| |
|
|
Abstract: A cyclic colouring of a plane 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$. It is conjectured that $\chic(G)\le\left\lfloor\frac32\Delta^{*}(G)\right\rfloor$ for any planar graph $G$ with a maximum face size $\Delta^{*}(G)$. Sanders and Zhao in [A new bound on the cyclic chromatic number, J. Combin. Theory Ser. B 83(2001), 102-111] proved that $\chic(G)\le\left\lceil \frac53\Delta^{*}(G)\right\rceil$ for any planar graph $G$. Their proof uses the Discharging Method and a knowledge of structural properties of a hypothetical minimal counterexample. In the present paper Lemma 2.5 of [Sanders and Y. Zhao, A new bound on the cyclic chromatic number, J. Combin. Theory Ser. B 83(2001), 102-111] about structural properties of a hypothetical minimal counterexample is generalized. Contact the authors: jana.zlamalova@upjs.sk Download PDF version of the preprint. |