• Abstract:   We study a simple Markov chain, known as the Glauber dynamics, for randomly sampling (proper) k-colorings of an input graph G on n vertices with maximum degree Δ and girth g. We prove the Glauber dynamics is close to the uniform distribution after O(n log n) steps whenever k>(1+ε)Δ, for all ε > 0, assuming g≥ 11 and Δ = Ω(log n). The best previously known bounds were k > 11Δ/6 for general graphs, and k > 1.489 Δ for graphs satisfying girth and maximum degree requirements.

  Our proof relies on the construction and analysis of a non-Markovian coupling. This appears to be the first application of a non-Markovian coupling to substantially improve upon known results.

Versions available:

Full version of July 18, 2005, 35pp	PDF	Postscript	DVI
Full version of July 24, 2003, 32pp	Available by request.
Conference proceedings version, 10pp (2-column)	PDF	Postscript	DVI