10.1184/R1/6479279.v1 Martin Dyer Martin Dyer Alan Frieze Alan Frieze Thomas P. Hayes Thomas P. Hayes Eric Vigoda Eric Vigoda Randomly coloring constant degree graphs Carnegie Mellon University 2013 Glauber dynamics Random colorings Coupling Technique 2013-09-23 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/Randomly_coloring_constant_degree_graphs/6479279 <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><sub>0</sub>(<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><sup>2</sup>) 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</p>