Borodin's cyclic coloring conjecture

Let GG be a connected plane graph with vertex set V(G)V(G), edge set E(G)E(G), and face set F(G)F(G). A cyclic coloring assigns distinct colors to any two different vertices incident with the same face. Write χc(G)\chi_c(G) for the minimum number of colors in such a coloring, and let Δ(G)\Delta^*(G) denote the maximum face degree of GG.

Borodin's cyclic coloring conjecture. Every connected plane graph GG satisfies

χc(G)32Δ(G).\chi_c(G) \leq \left\lfloor \frac{3}{2}\Delta^*(G) \right\rfloor.

The lower bound χc(G)Δ(G)\chi_c(G) \geq \Delta^*(G) is immediate, and Borodin showed that the conjectured upper bound, when true, is best possible. It is known for maximum face degree at most 44 and for maximum face degree 66, 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

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.