Title:
Interval edge colorings of Hamming graphs
Author:
Type:
Co-author(s) :
Abstract:
An edge-coloring of a graph G with colors 1,..., t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. For an interval colorable graph G, the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W (G), respectively. Hamming graph H(n1 ,...,nk ) is defined as a Cartesian product of complete graphs Kn1 ...Knk . Hamming graph H(n1 ,...,nk ) is interval colorable if and only if n1 · ... · nk is even. If H(n1 ,...,nk ) is interval colorable, then w(H(n1 ,...,nk )) is equal to its maximum degree and for every t between w(H(n1 ,...,nk )) and W (H(n1 ,...,nk )) it has an interval t-coloring. The exact value of W (H(n1 ,...,nk )) is not known even in the case k = 1. In this talk we present improved upper and lower bounds on W (H(n1 ,...,nk )).1
Language:
URL:
Affiliation:
Country:
Year:
Time period:
Conference title:
8th Slovenian Conferenceon Graph Theory