General upper-bound conjecture for interval cyclic colorings

Let GG be a connected graph with at least two vertices, let V(G)V(G) be its vertex set, and let Nc\mathfrak{N}_{c} denote the class of interval cyclically colorable graphs. Write Wc(G)W_c(G) for the maximum number of colors in an interval cyclic coloring. The general interval cyclic upper-bound conjecture.

Wc(G)2V(G)3.W_c(G)\leq 2\lvert V(G)\rvert-3.

This conjecture proposes removing the maximum-degree term from the previously proved general bound for connected interval cyclically colorable graphs. The paper also relates it to the triangle-free case, but does not establish either conjecture.

Sources & referencesView supporting material

Primary source

Petros A. Petrosyan and Sargis T. Mkhitaryan, “Interval cyclic edge-colorings of graphs”, arXiv:1411.0290 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.