Interval Edge-Colorings of Cartesian Products of Graphs I

Petrosyan, Petros A.  ; Khachatrian, Hrant H.  ; Tananyan, Hovhannes G. 

Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 613-632

Résumé

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 𝔑 be the set of all interval colorable graphs. For a 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. In this paper we first show that if G is an r-regular graph and G ∈𝔑, then W(G □ P_m) ≥ W(G) + W(P_m) + (m − 1)r (m ∈ℕ) 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 ∈𝔑 and w(G □ H) leq 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.