Premium
Randomly coloring graphs with lower bounds on girth and maximum degree
Author(s) -
Dyer Martin,
Frieze Alan
Publication year - 2003
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.10087
Subject(s) - glauber , combinatorics , mathematics , degree (music) , discrete mathematics , random graph , graph , girth (graph theory) , physics , acoustics , scattering , optics
We consider the problem of generating a random q ‐coloring of a graph G = ( V , E ). We consider the simple Glauber Dynamics chain. We show that if the maximum degree Δ > c 1 ln n and the girth g > c 2 ln Δ ( n = | V |) for sufficiently large c 1 , c 2 , then this chain mixes rapidly provided q /Δ > β, where β ≈ 1.763 is the root of β = e 1/β . For this class of graphs, this beats the 11Δ/6 bound of Vigoda E. Vigoda, Improved bounds for sampling colorings, Proc 40th Annu IEEE Symp Foundations of Computer Science, 1999, pp. 51–59 for general graphs. We extend the result to random graphs. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 167–179, 2003