Bonsma–Cereceda diameter conjecture for colouring graphs

Let $G$ be a graph of order $n$, let $\operatorname{col}(G)$ denote its colouring number, and let $\mathcal{C}_k(G)$ be its $k$-colouring reconfiguration graph.

Bonsma–Cereceda's conjecture. For $k\geq\operatorname{col}(G)+1$,

$$\operatorname{diam}(\mathcal{C}_k(G))=O(n^3).$$

This conjecture concerns polynomial bounds on the diameter of colouring reconfiguration graphs. Earlier results give quadratic bounds under stronger hypotheses, while superpolynomial distances can occur for smaller numbers of colours; the stated cubic bound remains unresolved here.