Randomly coloring planar graphs with fewer colors than the maximum degree |
| |
| Authors: | Thomas P. Hayes Juan C. Vera Eric Vigoda |
| |
| Affiliation: | 1. Department of Computer Science, University of New Mexico, Albuquerque, New Mexico;2. Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands;3. School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia |
| |
| 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 known as the Glauber dynamics for planar graphs when  . Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most  , for fixed  . The main challenge when  is the possibility of “frozen” vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when  , even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using “local uniformity” properties. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 731–759, 2015 |
| |
| Keywords: | Markov chain Monte Carlo random colorings approximate counting Glauber dynamics mixing time |
|
|
