Name
Abstract | ||
|---|---|---|
We study Markov chains for randomly sampling k-colorings of a graph with maximum degree δ. Our main result is a polynomial upper bound on the mixing time of the single-site update chain knownas the Glauber dynamics for planar graphs when k=Ω(δ/logδ). Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graphis at most δ1-ε, for fixed ε 0. The main challenge when k ≤ δ + 1 is the possibility of "frozen" vertices, that is, vertices for which only one coloris possible, conditioned on the colors of its neighbors. Indeed, when δ = O(1), even a typical coloring canhave a constant fraction of the vertices frozen.Our proofs rely on recent advances in techniquesfor bounding mixing time using "local uniformity" properties. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1250790.1250857 | Random Struct. Algorithms |
Keywords | Field | DocType |
Coupling,Graph coloring,Markov chain Monte Carlo (MCMC),Planar graphs | Complete coloring,Discrete mathematics,Edge coloring,Combinatorics,Fractional coloring,Degree (graph theory),Brooks' theorem,Greedy coloring,Planar graph,Mathematics,Graph coloring | Conference |
Volume | Issue | ISSN |
47 | 4 | 0737-8017 |
Citations | PageRank | References |
7 | 0.57 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas P. Hayes | 1 | 659 | 54.21 |
| Juan C. Vera | 2 | 50 | 7.98 |
| Eric Vigoda | 3 | 747 | 76.55 |