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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.