Reconfiguring 10-colourings of planar graphs

Abstract

Let $k\ge 1$ be an integer. The reconfiguration graph $R_k(G)$ of the $k$-colourings of a graph~$G$ has as vertex set the set of all possible $k$-colourings of $G$ and two colourings are adjacent if they differ on exactly one vertex. A conjecture of Cereceda from 2007 asserts that for every integer $\ell \ge k+2$ and $k$-degenerate graph $G$ on $n$ vertices, $R_{\ell }(G)$ has diameter $O(n^2)$. The conjecture has been verified only when $\ell \ge 2k+1$. We give a simple proof that if $G$ is a planar graph on $n$ vertices, then $R_{10}(G)$ has diameter at most $n^2$. Since planar graphs are $5$-degenerate, this affirms Cereceda's conjecture for planar graphs in the case $\ell =2k$.

5 pages; added a corollary and other minor changes