Loading...
Please wait, while we are loading the content...
Similar Documents
Randomly coloring constant degree graphs (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Dyer, Martin Frieze, Alan Vigoda, Eric Hayes, Thomas P. |
| Abstract | 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, for every ɛ> 0, the dynamics converges to a random coloring within O(n log n) steps assuming k ≥ k0(ɛ) and either: (i) k/ ∆> α + ɛ where α ∗ ≈ 1.763 and the girth g ≥ 5, or (ii) k/ ∆> β + ɛ where β ∗ ≈ 1.489 and the girth g ≥ 7. Previous results on this problem applied when k = Ω(log n), or when k> 11∆/6 for general graphs. 1 |
| File Format | |
| Publisher Date | 2004-01-01 |
| Publisher Institution | in Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS |
| Access Restriction | Open |
| Subject Keyword | Glauber Dynamic Dynamic Converges General Graph Maximum Degree Constant Degree Graph N-vertex Graph Random K-coloring Simple Markov Chain |
| Content Type | Text |
| Resource Type | Proceeding |
