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

About 10 years old · traced to

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.

References

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.