Cyclic Coloring of Plane Graphs with Maximum Face Size 16 and 17

2016/03/22 by Dvorak, Zdenek, Hebdige, Michael, Hlasek, Filip +2
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1603.06722

Abstract

Plummer and Toft conjectured in 1987 that the vertices of every 3-connected plane graph with maximum face size D can be colored using at most D+2 colors in such a way that no face is incident with two vertices of the same color. The conjecture has been proven for D=3, D=4 and D>=18. We prove the conjecture for D=16 and D=17.

Related

• Third case of the Cyclic Coloring Conjecture
• On the cyclic coloring conjecture
• Cyclic colorings of plane graphs with independent faces
• 3-facial colouring of plane graphs
• A note on 3-colorable plane graphs without 5- and 7-cycles