An \emph{ interval $t$-coloring} of a graph $G$ is a proper edge-coloring with colors $1,\dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors. A graph $G$ is called \emph{ interval colorable} if it has an interval $t$-coloring for some positive integer $t$. Let $\mathfrak{ N}$ be the set of all interval colorable graphs. For a graph $G\in \mathfrak{ N}$, we denote by $w(G)$ and $W(G)$ the minimum and maximum number of colors in an interval coloring of a graph $G$, respectively. In this paper we present some new sharp bounds on $W(G\square H)$ for graphs $G$ and $H$ satisfying various conditions. In particular, we show that if $G,H\in \mathfrak{ N}$ and $H$ is an $r$-regular graph, then $W(G\square H)\geq W(G)+W(H)+r$. We also derive a new upper bound on $W(G)$ for interval colorable connected graphs with additional distance conditions. Based on these bounds, we improve known lower and upper bounds on $W(C_{ 2n_{ 1}}\square C_{ 2n_{ 2}}\square\cdots \square C_{ 2n_{ k}})$ for $k$-dimensional tori $C_{ 2n_{ 1}}\square C_{ 2n_{ 2}}\square\cdots \square C_{ 2n_{ k}}$ and on $W(K_{ 2n_{ 1}}\square K_{ 2n_{ 2}}\square\cdots \square K_{ 2n_{ k}})$ for Hamming graphs $K_{ 2n_{ 1}}\square K_{ 2n_{ 2}}\square\cdots \square K_{ 2n_{ k}}$, and these new bounds coincide with each other for hypercubes. Finally, we give several results on interval colorings of Fibonacci cubes $\Gamma_{ n}$.
Categories: math.CO