Randomly coloring planar graphs with fewer colors than the maximum degree

T.P. Hayes, J.C. Vera Lizcano, E. Vigoda

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)


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 known as 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 graph is 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 color is possible, conditioned on the colors of its neighbors. Indeed, when Δ=Ο(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”
Original languageEnglish
Pages (from-to)731-759
JournalRandom Structures & Algorithms
Issue number4
Early online date1 Jul 2014
Publication statusPublished - Dec 2015


  • Markov chain Monte Carlo
  • random colorings
  • approximate counting
  • Glauber dynamics
  • mixing time


Dive into the research topics of 'Randomly coloring planar graphs with fewer colors than the maximum degree'. Together they form a unique fingerprint.

Cite this