3-Facial Coloring of Plane Graphs
Frédéric Havet, Jean‐Sébastien Sereni, Riste Škrekovski · SIAM Journal on Discrete Mathematics · 2008
A plane graph is ł-facially k-colorable if its vertices can be colored with k colors such that any two distinct vertices on a facial segment of length at most łare colored differently. We prove that every plane graph is 3-facially $11$-colorable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically $11$-colorable. These two bounds are just one higher than those that are proposed by the $(3\l+1)$-conjecture and the cyclic conjecture.