A polynomial version of Cereceda's conjecture

Let k and d be positive integers such that k >= 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 colouring 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, there is no proof of a polynomial upper bound on the diameter, 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 >= d+ 2. Moreover, we prove that if k >= 3/2 (d + 1) then the diameter of the k-reconfiguration graph is quadratic, improving the previous bound of k >= 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. (C) 2022 Elsevier Inc. All rights reserved.