Interval cyclic edge-colorings of graphs

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.