2015/08/01 by Petros A. Petrosyan, Petrosyan, Petros A., Hayk H. Tepanyan +1
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Cartesian product #Chordal graph #Combinatorics #Combinatorics (math.CO) #Computer science #Discrete Mathematics (cs.DM) #Discrete mathematics #Edge coloring #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Graph power #Integer (computer science) #Interval (graph theory) #Interval graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Vertex (graph theory) #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1508.00158
12 pages, 3 figures
arxiv created 2015/08/01 · openalex publication_date 2015/08/01 · arxiv updated 2015/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An edge-coloring of a graph G with consecutive integers c1,…,ct is called an interval t-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 \mathfrakN. In 2004, Giaro and Kubale showed that if G,H∈ \mathfrakN, then the Cartesian product of these graphs belongs to \mathfrakN. In the same year they formulated a similar problem for the composition of graphs as an open problem. Later, in 2009, the first author showed that if G,H∈ \mathfrakN and H is a regular graph, then G[H]∈ \mathfrakN. In this paper, we prove that if G∈ \mathfrakN and H has an interval coloring of a special type, then G[H]∈ \mathfrakN. 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∈ \mathfrakN and T is a tree, then G[T]∈ \mathfrakN.