Randomly coloring constant degree graphs |
| |
Authors: | Martin Dyer Alan Frieze Thomas P Hayes Eric Vigoda |
| |
Institution: | 1. School of Computer Studies, University of Leeds, Leeds LS2 9JT, UK;2. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh Pennsylvania 15213;3. Department of Computer Science, University of New Mexico, Albuquerque, New Mexico 87131;4. School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332 |
| |
Abstract: | We study a simple Markov chain, known as the Glauber dynamics, for generating a random k ‐coloring of an n ‐vertex graph with maximum degree Δ. We prove that, for every ε > 0, the dynamics converges to a random coloring within O(nlog n) steps assuming k ≥ k0(ε) and either: (i) k/Δ > α* + ε where α*≈? 1.763 and the girth g ≥ 5, or (ii) k/Δ >β * + ε where β*≈? 1.489 and the girth g ≥ 7. Our work improves upon, and builds on, previous results which have similar restrictions on k/Δ and the minimum girth but also required Δ = Ω (log n). The best known result for general graphs is O(nlog n) mixing time when k/Δ > 2 and O(n2) mixing time when k/Δ > 11/6. Related results of Goldberg et al apply when k/Δ > α* for all Δ ≥ 3 on triangle‐free “neighborhood‐amenable” graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 |
| |
Keywords: | Glauber dynamics Random colorings Coupling Technique |
|
|