A polynomial version of Cereceda's conjecture

Abstract

Let $k$ and $d$ be such that $k\ge d+2$. Consider two $k$-colourings of a $d$-degenerate graph $G$. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length. The $k$-reconfiguration graph of $G$ is the graph whose vertices are the proper $k$-colourings of $G$, with an edge between two colourings if they differ on exactly one vertex. Cereceda's conjecture can be reformulated as follows: the diameter of the $(d+2)$-reconfiguration graph of any $d$-degenerate graph on $n$ vertices is $O(n^2)$. So far, the existence of a polynomial diameter is open even for $d=2$. In this paper, we prove that the diameter of the $k$-reconfiguration graph of a $d$-degenerate graph is $O(n^{d+1})$ for $k\ge d+2$. Moreover, we prove that if $k\ge \frac{3}{2}(d+1)$ then the diameter of the $k$-reconfiguration graph is quadratic, improving the previous bound of $k\ge 2d+1$. We also show that the $5$-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs.

14 pages