Petrosyan–Mkhitaryan conjecture on cyclic interval colorings

Let Nc\mathfrak{N}_c be the class of multigraphs admitting a cyclic interval coloring, and let Wc(G)W_c(G) denote the maximum number of colors in a cyclic interval coloring of GG. Petrosyan–Mkhitaryan conjecture.

(i) For every triangle-free graph GNcG\in\mathfrak{N}_c,

Wc(G)V(G).W_c(G)\leq \lvert V(G)\rvert.

(ii) For every graph GNcG\in\mathfrak{N}_c with at least two vertices,

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

The paper states that the first bound is known for graphs of maximum degree at most 44, while the general assertions are presented as conjectures; the second bound extends the corresponding general upper-bound question beyond triangle-free graphs.

Sources & referencesView supporting material

Primary source

Carl Johan Casselgren, Hrant H. Khachatrian and Petros A. Petrosyan, “Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs”, arXiv:1611.07011 (2016).

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.