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.}

Back to all abstracts