Co-author(s) :

Petrosyan Petros

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

Identifier:

oai:noad.sci.am:135903

Language:

English

URL:

Affiliation:

Yerevan State University

Country:

Slovenia

Year:

2015

Time period:

June 21 – 27

Conference title:

8th Slovenian Conferenceon Graph Theory

Place:

Kranjska Gora

Participation type:

oral