Another step towards proving a conjecture by Plummer and Toft

A cyclic colouring of a graph GG embedded in a surface is a vertex colouring of GG in which any two distinct vertices sharing a face receive distinct colours. The cyclic chromatic number χc(G) of GG is the smallest number of colours in a cyclic colouring of GG. 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 GG with maximum face degree Δ∗Δ∗. It is known that the conjecture holds true for Δ∗≤4Δ∗≤4 and Δ∗≥24Δ∗≥24. The validity of the conjecture is proved in the paper for Δ∗≥18Δ∗≥18.