Interval edge-colorings of Cartesian products of graphs I

Abstract

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