Another step towards proving a conjecture by Plummer and Toft

A cyclic colouring of a graph G embedded in a surface is a vertex colouring of G in which any two distinct vertices sharing a face receive distinct colours. The cyclic chromatic number χ c ( G ) of G is the smallest number of colours in a cyclic colouring of G . Plummer and Toft in 1987 [M.D. Plummer, B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987) 507–515] conjectured that χ c ( G ) ≤ Δ ∗ + 2 for any 3-connected plane graph G with maximum face degree Δ ∗ . It is known that the conjecture holds true for Δ ∗ ≤ 4 and Δ ∗ ≥ 24 . The validity of the conjecture is proved in the paper for Δ ∗ ≥ 18 .