Randomly coloring constant degree graphs1. Issue 2 (3rd August 2012)

• Record Type: Journal Article
• Authors: Dyer, Martin; Frieze, Alan; Hayes, Thomas P.; Vigoda, Eric
• Is Part Of: Random structures & algorithms. Volume 43:Issue 2(2013)
• Page Start: 181
• Page End: 200
• Publication Date: 2012-08-03
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20451
• Languages: English
• ISSNs: 1042-9832

Abstract

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