Interval edge colorings of some products of graphs

الأصل · EN

An edge coloring of a graph G with colors 1,2,,t is called an interval t-coloring if for each i∈ {1,2,,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t≥ 1 for which G has an interval t-coloring. Let N be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H∈ N, then the Cartesian product of these graphs belongs to N. Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G∈ N, then G[nK₁]∈ N for any n∈ N. Furthermore, we show that if G,H∈ N and H is a regular graph, then strong and lexicographic products of graphs G,H belong to N. We also prove that tensor and strong tensor products of graphs G,H belong to N if G∈ N and H is a regular graph.