A general upper bound for the cyclic chromatic number of 3‐connected plane graphs
Hikoe Enomoto, Mirko Horňák · Journal of Graph Theory · 2009
Abstract The cyclic chromatic number of a plane graph G is the smallest number χc(G) of colors that can be assigned to vertices of G in such a way that whenever two distinct vertices are incident with a common face, they receive distinct colors. It was conjectured by Plummer and Toft in 1987 that, for every 3‐connected plane graph G, χc(G)≤Δ*(G) + 2, where Δ*(G) is the maximum face degree of G. The best upper bound known so far was Δ*(G) + 8. In the paper this bound is improved to Δ*(G) + 5. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 1–25, 2009