Plummer–Toft conjecture on cyclic coloring of 3-connected plane graphs

Let GG be a 33-connected plane graph, and let Δ\Delta^\star be its maximum face size. A cyclic coloring of GG is a vertex coloring in which any two vertices incident with the same face receive distinct colors. Plummer–Toft's conjecture. Every 33-connected plane graph with maximum face size Δ\Delta^\star has a cyclic coloring with at most Δ+2\Delta^\star+2 colors. The conjecture is known for Δ=3\Delta^\star=3, Δ=4\Delta^\star=4, and Δ18\Delta^\star\ge 18, and this paper proves the cases Δ=16\Delta^\star=16 and Δ=17\Delta^\star=17; the remaining values are not resolved here.

Sources & referencesView supporting material

Primary source

Zdenek Dvorak, Michael Hebdige, Filip Hlasek, Daniel Kral and Jonathan Noel, “Cyclic Coloring of Plane Graphs with Maximum Face Size 16 and 17”, arXiv:1603.06722 (2020).

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.