Randomly coloring constant degree graphs

<p>We study a simple Markov chain, known as the Glauber dynamics, for generating a random <em>k</em> -coloring of an <em>n</em> -vertex graph with maximum degree Δ. We prove that, for every <em>ε</em> > 0, the dynamics converges to a random coloring within <em>O</em>(<em>n</em>log <em>n</em>) steps assuming <em>k</em> ≥ <em>k</em>₀(<em>ε</em>) and either: (i) <em>k</em>/Δ > α* + <em>ε</em> where α*≈ 1.763 and the girth <em>g</em> ≥ 5, or (ii) <em>k</em>/Δ >β * + <em>ε</em> where β*≈ 1.489 and the girth <em>g</em> ≥ 7. Our work improves upon, and builds on, previous results which have similar restrictions on <em>k</em>/Δ and the minimum girth but also required Δ = Ω (log <em>n</em>). The best known result for general graphs is <em>O</em>(<em>n</em>log <em>n</em>) mixing time when <em>k</em>/Δ > 2 and <em>O</em>(<em>n</em>²) mixing time when <em>k</em>/Δ > 11/6. Related results of Goldberg et al apply when <em>k</em>/Δ > α* for all Δ ≥ 3 on triangle-free “neighborhood-amenable” graphs