Interval edge-colorings of Cartesian products of graphs I
Hrant Khachatrian, Petros A. Petrosyan, Hovhannes G. Tananyan · Discussiones Mathematicae Graph Theory · 2013
A proper 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 form an interval of integers.A graph G is interval colorable if it has an interval t-coloring for some positive integer t.Let N be the set of all interval colorable graphs.For a graph G ∈ N, 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.In this paper we first show that if G is an r-regular graph and G ∈ N, then W (G P m ) ≥ W (G) + W (P m ) + (m -1)r (m ∈ N) and W (G C 2n ) ≥ W (G) + W (C 2n ) + nr (n ≥ 2).Next, we investigate interval edge-colorings of grids, cylinders and tori.In particular, we prove that if G H is planar and both factors have at least 3 vertices, then G H ∈ N and w(G H) ≤ 6.Finally, we confirm the first author's conjecture on the n-dimensional cube Q n and show that Q n has an interval t-coloring if and only if n ≤ t ≤ n(n+1) 2 .