On a conjecture by Plummer and Toft
Mirko Horňák, Stanislav Jendrol′ · Journal of Graph Theory · 1999
The cyclic chromatic number χc(G) of a 2-connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face-bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3-connected plane graph G, under the assumption Δ*(G) ≥ 42, where Δ*(G) is the size of a largest face of G, it holds that χc(G) ≤ Δ*(G) + 4. They conjectured that, if G is a 3-connected plane graph, then χc>(G) ≤ Δ*(G) + 2. In the article the conjecture is proved for Δ*(G) ≥ 24. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 177–189, 1999