Abstract:
We study a simple Markov chain, known as the Glauber dynamics, for generating a random k-coloring of a n-vertex graph with maximum degree Δ. We prove that the dynamics converges to a random coloring after O(n log n) steps assuming k ≥ k₀ for some absolute constant k₀, and either: (i) k/Δ > α^* = 1.763... and the girth g ≥ 5, or (ii) k/Δ > β^* = 1.489... and the girth g ≥ 6. Previous results on this problem applied when k = Ω(log n), or when k > 11Δ/6 for general graphs.