Interval edge-colorings of composition of graphs

详细信息    查看全文

• 作者：H.H. Tepanyan^a ; ^{tehayk@stanford.edu} ; P.A. Petrosyan^b ; ^c ; ^{pet_petros@ipia.sci.am}
• 关键词：Edge-coloring ; Interval coloring ; Composition of graphs ; Complete bipartite graph ; Tree
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：368-374
• 全文大小：722 K
• 卷排序：217

文摘

An edge-coloring of a graph GG with consecutive integers c1,…,ctc1,…,ct is called an interval  tt-coloring   if all colors are used, and the colors of edges incident to any vertex of GG are distinct and form an interval of integers. A graph GG is interval colorable if it has an interval tt-coloring for some positive integer tt. The set of all interval colorable graphs is denoted by NN. In 2004, Giaro and Kubale showed that if G,H∈NG,H∈N, then the Cartesian product of these graphs belongs to NN. In the same year they formulated a similar problem for the composition of graphs as an open problem. Later, in 2009, the second author showed that if G,H∈NG,H∈N and HH is a regular graph, then G[H]∈NG[H]∈N. In this paper, we prove that if G∈NG∈N and HH has an interval coloring of a special type, then G[H]∈NG[H]∈N. Moreover, we show that all regular graphs, complete bipartite graphs and trees have such a special interval coloring. In particular, this implies that if G∈NG∈N and TT is a tree, then G[T]∈NG[T]∈N.