Glauber dynamics on proper colorings mixes in $O(n\log n)$ for $q>2\Delta$

Let $G$ be a graph on $n$ vertices with maximum degree $\Delta$, and fix a number of colors $q$. A $q$-coloring of the vertices is proper when adjacent vertices receive distinct colors, and the Glauber dynamics on proper colorings picks a uniform vertex and re-samples its color from the uniform distribution on the colorings that agree with the current one elsewhere — that is, uniformly among the colors legal at that vertex. Its stationary distribution is uniform over proper colorings. For a tolerance $\varepsilon$, the mixing time $t_{\mathrm{mix}}(\varepsilon)$ is the first $t$ with $\max_x\|P^t(x,\cdot)-\pi\|_{TV}\le\varepsilon$, where $\|\mu-\nu\|_{TV}=\max_A|\mu(A)-\nu(A)|$ is the total variation distance.

The theorem (Theorem 14.8 of Levin–Peres–Wilmer, the capstone of Chapter 14) asserts: if $q>2\Delta$, then for every $0<\varepsilon<1$,

With a bit more than twice as many colors as the maximum degree, the dynamics mixes in order $n\log n$ steps. This is the flagship application of path coupling: colorings differing at one vertex are coupled by matching their proposed recolorings, and the single-edge contraction rate $(q-2\Delta)/\bigl(n(q-\Delta)\bigr)$ falls out of counting the disagreeing proposals.