کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646704 | 1342310 | 2016 | 13 صفحه PDF | دانلود رایگان |
A proper edge-coloring αα of a graph GG with colors 1,…,t1,…,t is called an interval cyclic tt-coloring if all colors are used, and the colors of edges incident to each vertex vv of GG either form an interval of integers or the set {1,…,t}∖{α(e):eisincidenttov} is an interval of integers. A graph GG is interval cyclically colorable if it has an interval cyclic tt-coloring for some positive integer tt. The set of all interval cyclically colorable graphs is denoted by NcNc. For a graph G∈NcG∈Nc, the least and the greatest values of tt for which it has an interval cyclic tt-coloring are denoted by wc(G)wc(G) and Wc(G)Wc(G), respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if GG is a triangle-free graph with at least two vertices and G∈NcG∈Nc, then Wc(G)≤|V(G)|+Δ(G)−2Wc(G)≤|V(G)|+Δ(G)−2. We also obtain some bounds on wc(G)wc(G) and Wc(G)Wc(G) for various classes of graphs. Finally, we give two methods for constructing of interval cyclically non-colorable graphs.
Journal: Discrete Mathematics - Volume 339, Issue 7, 6 July 2016, Pages 1848–1860