Petrosyan–Mkhitaryan conjecture on cyclic interval colorings
Petrosyan–Mkhitaryan conjecture on cyclic interval colorings
Let be the class of multigraphs admitting a cyclic interval coloring, and let denote the maximum number of colors in a cyclic interval coloring of . Petrosyan–Mkhitaryan conjecture.
(i) For every triangle-free graph ,
(ii) For every graph with at least two vertices,
The paper states that the first bound is known for graphs of maximum degree at most , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.