Interval edge-colorings of Cartesian products of graphs II

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\mathrm{\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\mathrm{\square }H)\ge 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}\mathrm{\square }{C}_{2n_2}\mathrm{\square }\cdots \mathrm{\square }{C}_{2n_k})$ for $k$-dimensional tori $C_{2n_1}\mathrm{\square }{C}_{2n_2}\mathrm{\square }\cdots \mathrm{\square }{C}_{2n_k}$ and on $W(K_{2n_1}\mathrm{\square }{K}_{2n_2}\mathrm{\square }\cdots \mathrm{\square }{K}_{2n_k})$ for Hamming graphs $K_{2n_1}\mathrm{\square }{K}_{2n_2}\mathrm{\square }\cdots \mathrm{\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 ${\mathrm{\Gamma }}_n$.