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 . Our main result is a polynomial upper bound on the mixing time of the single-site update chain knownas the Glauber dynamics for planar graphs when k=(/log). Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graphis at most ^1-, for fixed > 0. The main challenge when k + 1 is the possibility of "frozen" vertices, that is, vertices for which only one coloris possible, conditioned on the colors of its neighbors. Indeed, when = O(1), even a typical coloring canhave a constant fraction of the vertices frozen.Our proofs rely on recent advances in techniquesfor bounding mixing time using "local uniformity" properties.