| |
|
|
Abstract: 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 $\chic(G)$ of $G$ is the smallest number of colours in a cyclic colouring of $G$. Plummer and Toft in~1987 conjectured that $\chic(G)\le\Delta^*+2$ for any 3-connected plane graph $G$ with maximum face degree $\Delta^*$. It is known that the conjecture holds true for $\Delta^*\le4$ and $\Delta^*\ge24$. The validity of the conjecture is proved in the paper for $\Delta^*\ge18$. Contact the authors: mirko.hornak@upjs.sk, jana.zlamalova@upjs.sk Download PDF version of the preprint. |