Randomly coloring planar graphs with fewer colors than the maximum degree

We study Markov chains for randomly sampling $k$-colorings of a graph with maximum degree $\mathrm{\Delta }$. Our main result is a polynomial upper bound on the mixing time of the single-site update chain known as the Glauber dynamics for planar graphs when $k=\mathrm{\Omega }(\mathrm{\Delta }\mathrm{/}\log \mathrm{\Delta })$. Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most ${\mathrm{\Delta }}^{1-\text{eps}}$, for fixed $\eps > 0$. The main challenge when $k\le \mathrm{\Delta }+1$ is the possibility of “frozen” vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when $\mathrm{\Delta }=O(1)$, even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using “local uniformity” properties.