Colouring planar graphs with a precoloured induced cycle

Abstract

Let $C$ be a cycle and $f:V(C)\to \{c_1,c_2,\dots ,c_k\}$ a proper $k$-colouring of $C$ for some $k\ge 4$. We say the colouring $f$ is safe if for any planar graph $G$ in which $C$ is an induced cycle, there exists a proper $k$-colouring $f^{\prime }$ of $G$ such that $f^{\prime }(v)=f(v)$ for all $v\in V(C)$. The only safe $4$-colouring is any proper colouring of a triangle. We give a simple necessary condition for a $k$-colouring of a cycle to be safe and conjecture that it is sufficient for all $k\ge 4$. The sufficiency for $k=4$ follows from the four colour theorem and we prove it for $k=5$, independent of the four colour theorem. We show that a stronger condition is sufficient for all $k\ge 4$. As a consequence, it follows that any proper $k$-colouring of a cycle that uses at most $k-3$ distinct colours is safe. Also, any proper $k$-colouring of a cycle of length at most $2k-5$ that uses at most $k-1$ distinct colours is safe.

18 pages