On vertex types and cyclic colourings of 3-connected plane graphs (Q1970582)

Let \(G\) be a 3-connected plane graph, \(\Delta^*(G)\) the size of its largest face and \(\chi_c(G)\leq k+2\) its cyclic chromatic number, that is the minimum number of colors required for a vertex coloring of \(G\) where all vertices adjacent to the same face have different colors. It is then shown that it must contain a vertex of a certain `type' (the definition is technical and involves the size of faces adjacent to it as well as to its degree), unless a given configuration occurs in the graph. This result is applied to prove the inequality \(\chi_c(G)\leq k+2\) where \(k= \max\{40, \Delta^*(G)\}\). The latter result settles (for \(\Delta^*(G)\leq 40\)) the conjecture of \textit{M. D. Plummer} and \textit{B. Toft} [J. Graph Theory 11, No. 4, 507-515 (1987; Zbl 0655.05030)], stating that \(\chi_c(G)\leq \Delta^*(G)k+ 2\).