Randomly coloring planar graphs with fewer colors than the maximum degree

December 11, 2006
Juan C. Vera | Georgia Institute of Technology

We study Markov chains for randomly sampling k-colorings of a graph with maximum degree D. We prove the first results, for a general class of graphs, showing fast convergence of such chains when the number of colors k << D.

When D =O((log n)^(1+eps)) and k > D/log D we prove O(n log n) mixing time of the single-site update chain, known as the Glauber dynamics, for any planar graph. This result is tight, there exist planar graphs for which the Glauber dynamics has super-polynomial mixing time whenever k = o(D/ log D).

A challenging aspect of the case when D is constant and k D/ log D. This implies polynomial mixing time of the original Glauber dynamics under the same conditions.

Joint work with Thomas P. Hayes and Eric Vigoda.

Speaker Details

Juan Vera is a post-doctoral researcher at Georgia Tech, working with Eric Vigoda. He recently completed his Ph.D. at CMU, where he worked with Alan Frieze on analyzing models of power-law graphs. He has also worked extensively on positive polynomial optimization and soccer.