Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949809 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
An edge-coloring of a graph G with consecutive integers c1,â¦,ct is called an intervalt-coloring if all colors are used, 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 it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by N. In 2004, Giaro and Kubale showed that if G,HâN, then the Cartesian product of these graphs belongs to N. 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âN and H is a regular graph, then G[H]âN. In this paper, we prove that if GâN and H has an interval coloring of a special type, then G[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âN and T is a tree, then G[T]âN.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
H.H. Tepanyan, P.A. Petrosyan,