Cyclic chromatic number of 3-connected plane graphs (Q2706194)

Two vertices of a plane graph \(G\) are said to be cyclically adjacent if they are incident with a common face of \(G\). A vertex coloring of \(G\) is called a cyclic coloring if it assigns different colors to any pair of cyclically adjacent vertices. The minimum number of colors necessary for a cyclic coloring of \(G\) is called the cyclic chromatic number of \(G\) and is denoted by \(\chi _{c}(G)\). Let \(G\) be a 3-connected plane graph. \textit{M. D. Plummer} and \textit{B. Toft} [J. Graph Theory 11, No. 4, 507-515 (1987; Zbl 0655.05030)] conjectured that \(\chi _{c}(G)\leq \Delta ^{*}(G)+2\), where \(\Delta ^{*}(G)\) is the maximum face size of \(G\). \textit{M. Horňák} and \textit{S. Jendrol'} [J. Graph Theory 30, No. 3, 177-189 (1999; Zbl 0928.05021)] and \textit{O. V. Borodin} and \textit{D. R. 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 it is proved that \(\chi _{c}(G)\leq \Delta ^{*}(G)+1\) holds if \(\Delta ^{*}(G)\geq 60\).