Randomly coloring constant degree graphs

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.