Paper Info
Title
Randomly coloring graphs of girth at least five
Abstract
We improve rapid mixing results for the simple Glauber dynamics designed to generate a random k-coloring of a bounded-degree graph.Let G be a graph with maximum degree Δ = Ω(log n), and girth ≥ 5. We prove that if k Α Δ, where Α ≈ 1.763 then Glauber dynamics has mixing time O(n log n). If girth(G) ≥ 6 and k Β Δ, where Β ≈ 1.489 then Glauber dynamics has mixing time O(n log n). This improves a recent result of Molloy, who proved the same conclusion under the stronger assumptions that Δ=Ω(log n) and girth Ω(log Δ). Our work suggests that rapid mixing results for high girth and degree graphs may extend to general graphs.Analogous results hold for random graphs of average degree up to n¼, compared with polylog(n), which was the best previously known.Some of our proofs rely on a new Chernoff-Hoeffding type bound, which only requires the random variables to be well-behaved with high probability. This tail inequality may be of independent interest.
Year
DOI
Venue
2003
10.1145/780542.780584
STOC
Keywords
Field
DocType
random k-coloring,random graph,maximum degree,degree graph,average degree,glauber dynamic,high girth,time o,n log n,randomly coloring graph,log n,markov chain monte carlo,random variable,mixing time,graph coloring,chernoff bounds
Discrete mathematics,Glauber,Binary logarithm,Random variable,Combinatorics,Random graph,Degree (graph theory),Time complexity,Chernoff bound,Mathematics,Graph coloring
Conference
ISBN
Citations 
PageRank 
1-58113-674-9
21
1.45
References 
Authors
10
1
Name
Order
Citations
PageRank
Thomas P. Hayes165954.21