Cereceda–van den Heuvel–Johnson conjecture for graph recoloring

Let $G$ be a graph and let $k$ be an integer with $k\geq 4$. A $k$-coloring of $G$ is a proper vertex coloring using colors from a set of $k$ colors, and $k$-Mixing asks whether any two $k$-colorings of $G$ can be transformed into one another by repeatedly recoloring a single vertex while maintaining a proper $k$-coloring. Cereceda–van den Heuvel–Johnson conjecture. For every $k\geq 4$, $k$-Mixing is PSPACE-complete. This conjecture concerns the computational complexity of reconfiguring graph colorings; the paper proves the corresponding PSPACE-completeness result for $k\geq 4$ under the stated theorem's setting, while the general conjecture as recorded here is attributed to Cereceda, van den Heuvel and Johnson.