TY - GEN
T1 - Randomly coloring constant degree graphs
AU - Dyer, Martin
AU - Frieze, Alan
AU - Hayes, Thomas P.
AU - Vigoda, Eric
PY - 2004
Y1 - 2004
N2 - We study a simple Markov chain, known as the Glauber dynamics, for generating a random k-coloring of a n-vertex graph with maximum degree Δ. We prove that the dynamics converges to a random coloring after O(n log n) steps assuming k ≥ k0 for some absolute constant k0, and either: (i) k/Δ > α* ≈ 1.763 and the girth g ≥ 5, or (ii) k/Δ > β* ≈ 1.489 and the girth g ≥ 6. Previous results on this problem applied when k = Ω(log n), or when k > 11Δ/6 for general graphs.
AB - We study a simple Markov chain, known as the Glauber dynamics, for generating a random k-coloring of a n-vertex graph with maximum degree Δ. We prove that the dynamics converges to a random coloring after O(n log n) steps assuming k ≥ k0 for some absolute constant k0, and either: (i) k/Δ > α* ≈ 1.763 and the girth g ≥ 5, or (ii) k/Δ > β* ≈ 1.489 and the girth g ≥ 6. Previous results on this problem applied when k = Ω(log n), or when k > 11Δ/6 for general graphs.
UR - https://www.scopus.com/pages/publications/17744389641
U2 - 10.1109/FOCS.2004.57
DO - 10.1109/FOCS.2004.57
M3 - Conference contribution
AN - SCOPUS:17744389641
SN - 0769522289
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 582
EP - 589
BT - Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Sciences, FOCS 2004
PB - IEEE Computer Society
T2 - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004
Y2 - 17 October 2004 through 19 October 2004
ER -