Name
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 the dynamics converges to a random coloring after 0(n log n) steps assuming k 驴 k_0 for some absolute constnat k_0, and either: (i) {k \mathord{\left/ {\vphantom {k \Delta }} \right. \kern-\nulldelimiterspace} \Delta } 驴* 驴 1.763 and the girth g 驴 5, or (ii) {k \mathord{\left/ {\vphantom {k \Delta }} \right. \kern-\nulldelimiterspace} \Delta } β* 驴 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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/FOCS.2004.57 | Random Structures and Algorithms |
Keywords | Field | DocType |
markov processes,computational complexity,graph colouring,glauber dynamics,markov chain,constant degree graphs,random coloring | Discrete mathematics,Glauber,Graph,Binary logarithm,Combinatorics,Vertex (graph theory),struct,Markov chain,Degree (graph theory),Mathematics | Conference |
Volume | Issue | ISSN |
43 | 2 | 0272-5428 |
ISBN | Citations | PageRank |
0-7695-2228-9 | 21 | 1.66 |
References | Authors | |
14 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Dyer | 1 | 1029 | 97.62 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Thomas P. Hayes | 3 | 659 | 54.21 |
| Eric Vigoda | 4 | 747 | 76.55 |