CYCLIC CHROMATIC NUMBER OF 3-CONNECTED PLANE GRAPHS.

Let G be a 3-connected plane graph. Plummer and Toft [J. Graph Theory, 11 (1987), pp. 507–515] conjectured that χc(G) ≤ Δ*(G) + 2, where χc(G) is the cyclic chromatic number of G and Δ*(G) the maximum face size of G. Horňák and Jendrol' [J. Graph Theory, 30 (1999), pp. 177–189] and Borodin and Woodall [SIAM J. Discrete Math., submitted] independently proved this conjecture when Δ*(G) is large enough. Moreover, Borodin and Woodall proved a stronger statement that χc(G) ≤ Δ*(G) + 1 holds if Δ*(G) ≥ 122. In this paper, we prove that χc(G) ≤ Δ*(G) + 1 holds if Δ*(G) ≥ 60. [ABSTRACT FROM AUTHOR]