2014/11/02 by Petros A. Petrosyan, Petrosyan, Petros A., Sargis T. Mkhitaryan +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1411.0290
23 pages, 5 figures
arxiv created 2014/11/02 · arxiv updated 2014/11/04
A proper edge-coloring of a graph G with colors 1,…,t is called an interval cyclic t-coloring if all colors are used, and the edges incident to each vertex v∈ V(G) are colored by dG(v) consecutive colors modulo t, where dG(v) is the degree of a vertex v in G. A graph G is interval cyclically colorable if it has an interval cyclic t-coloring for some positive integer t. The set of all interval cyclically colorable graphs is denoted by \mathfrakNc. For a graph G∈ \mathfrakNc, the least and the greatest values of t for which it has an interval cyclic t-coloring are denoted by wc(G) and Wc(G), respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if G is a triangle-free graph with at least two vertices and G∈ \mathfrakNc, then Wc(G)≤ \vert V(G)\vert +Δ(G)-2. We also obtain bounds on wc(G) and Wc(G) for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.