A polynomial version of Cereceda's conjecture (Q2131856)

A \(k\)-coloring of \(G\) is a function \(f\colon V(G)\rightarrow \{1,\dots,k\}\) such that the coloring is proper. The \(k\)-reconfiguration graph of \(G\), denoted by \(\mathcal{G}(G,k)\), is the graph whose vertices are \(k\)-colorings of \(G\), and two \(k\)-colorings are adjacent if they differ on exactly one vertex. A graph \(G\) is \(d\)-degenerate if any subgraph of \(G\) has a vertex of degree at most \(d\). It is known that for any \(d\)-degenerate graph \(G\) and every \(k\ge d+2\), \(\mathcal{G}(G,k)\) is connected. \textit{L. Cereceda} [Mixing graph colourings. London: London School of Economics and Political Science (PhD Thesis) (2007), \url{http://etheses.lse.ac.uk/131/1/Cereceda_Mixing_graph_colourings.pdf}] conjectured that 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 the paper, the authors prove that the diameter of the \(k\)-reconfiguration graph of a \(d\)-degenerate graph is \(O(n^{d+1})\) for \(k\ge d+2\). Also, they prove that if \(k\ge3(d+1)/2\), then the diameter of the \(k\)-reconfiguration graph is quadratic, improving the previous bound of \(k\ge2d+1\). Moreover, the authors show that Cereceda's conjecture is true for the \(5\)-reconfiguration graph of planar bipartite graphs.