Premium
Randomly coloring constant degree graphs
Author(s) -
Dyer Martin,
Frieze Alan,
Hayes Thomas P.,
Vigoda Eric
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20451
Subject(s) - combinatorics , glauber , mathematics , constant (computer programming) , degree (music) , markov chain , vertex (graph theory) , mixing (physics) , graph , discrete mathematics , binary logarithm , physics , computer science , statistics , acoustics , programming language , quantum mechanics , scattering , optics
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 ( n log n ) steps assuming k ≥ k 0 ( ε ) 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 ( n log n ) mixing time when k /Δ > 2 and O ( n 2 ) 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