A note on cyclic chromatic number
Jana Zlámalová · Discussiones Mathematicae Graph Theory · 2010
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 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 ∆ ≥ 18. The validity of the conjecture is proved in the paper for some special classes of planar graphs.