Cyclic Chromatic Number of 3-Connected Plane Graphs
Hikoe Enomoto, Mirko Horňák, Stanislav Jendrol′ · SIAM Journal on Discrete Mathematics · 2001
Let G be a 3-connected plane graph. Plummer and Toft [ J. Graph Theory, 11 (1987), pp. 507--515] conjectured that $\chi_{c}(G) \leq \Delta^{*}(G) + 2$, where $\chi_{c}(G)$ is the cyclic chromatic number of G and $\Delta^{*}(G)$ the maximum face size of G. Horná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 $\Delta^{*}(G)$ is large enough. Moreover, Borodin and Woodall proved a stronger statement that $\chi_{c}(G) \leq \Delta^{*}(G) + 1$ holds if $\Delta^{*}(G) \geq 122$. In this paper, we prove that $\chi_{c}(G) \leq \Delta^{*}(G) + 1$ holds if $\Delta^{*}(G)\geq 60$.