Cereceda's conjecture

It follows from this that an appropriately designed random walk on the space of (d + 2)-colorings, using moves of this type, is mixing.

If the diameter is exponentially large in the number n of vertices in the graph, then the Glauber dynamics on colorings is certainly not rapidly mixing.

In his 2007 doctoral dissertation, Cereceda investigated this problem, and found that (even for connected components of the space of colors) the diameter can be exponential for (d + 1)-colorings of d-degenerate graphs.

He wrote that "it remains to determine" whether the diameter is polynomial for numbers of colors between these two extremes, or whether it is "perhaps even quadratic".

Alternatives include the Kempe dynamics in which one repeatedly finds and swaps the colors of Kempe chains,[8] and the "heat bath" dynamics in which one chooses pairs of adjacent vertices and a valid recoloring of that pair.

These moves may have stronger mixing properties and lower diameter of the space of colorings.

The 3-colorings of a path graph , which has degeneracy one. The diameter of this space of colorings is four: it takes four steps to get from either of the top two colorings to the bottom one.