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>