Prefer a chat interface with context about you and your work?
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 …