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 0(n log n) steps assuming k ≥ k_0 for some absolute constnat k_0, and either: (i) {k \mathord{\left/ {\vphantom {k \Delta }} \right. \kern-\nulldelimiterspace} \Delta } > α* ≈ 1.763 and the girth g ≥ 5, or (ii) {k \mathord{\left/ {\vphantom {k \Delta }} \right. \kern-\nulldelimiterspace} \Delta } > β* ≈ 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.