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