# Interval edge colorings of Hamming graphs

###
Hrant Khachatrian

Yerevan State University

####
Petros Petrosyan

Yerevan State University; Institute for Informatics and Automation Problems of NAS RA

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**Content:**
An edge-coloring of a graph $G$ with colors $1,\ldots,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(n_1,\ldots,n_k)$ is defined as a Cartesian product of complete graphs $K_{n_1}\square \ldots \square K_{n_k}$. Hamming graph $H(n_1,\ldots,n_k)$ is interval colorable if and only if $n_1\cdot \ldots \cdot n_k$ is even. If $H(n_1,\ldots,n_k)$ is interval colorable, then $w(H(n_1,\ldots,n_k))$ is equal to its maximum degree and for every $t$ between $w(H(n_1,\ldots,n_k))$ and $W(H(n_1,\ldots,n_k))$ it has an interval $t$-coloring. The exact value of $W(H(n_1,\ldots,n_k))$ is not known even in the case $k=1$. In this talk we present improved upper and lower bounds on $W(H(n_1,\ldots,n_k))$.\footnote{This work was made possible by a research grant from the Armenian National Science and Education Fund (ANSEF) based in New York, USA.}