Borodin's cyclic coloring conjecture
Borodin's cyclic coloring conjecture
Let be a connected plane graph with vertex set , edge set , and face set . A cyclic coloring assigns distinct colors to any two different vertices incident with the same face. Write for the minimum number of colors in such a coloring, and let denote the maximum face degree of .
Borodin's cyclic coloring conjecture. Every connected plane graph satisfies
The lower bound is immediate, and Borodin showed that the conjectured upper bound, when true, is best possible. It is known for maximum face degree at most and for maximum face degree , and holds asymptotically up to an arbitrarily small additive factor, but remains open in general.
Sources & referencesView supporting material
Primary source
Stanislav Jendrol and Roman Sotak, “On the cyclic coloring conjecture”, arXiv:2009.10436 (2020).
Additional references
2 papers in this index state this conjecture (2008–2020). The statement above is taken from the most recent of them; the others are arXiv:0812.1345.
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.