### Abstract

Original language | English |
---|---|

Pages (from-to) | 731-759 |

Journal | Random Structures & Algorithms |

Volume | 47 |

Issue number | 4 |

Early online date | 1 Jul 2014 |

DOIs | |

Publication status | Published - Dec 2015 |

### Fingerprint

### Keywords

- Markov chain Monte Carlo
- random colorings
- approximate counting
- Glauber dynamics
- mixing time

### Cite this

*Random Structures & Algorithms*,

*47*(4), 731-759. https://doi.org/10.1002/rsa.20560

}

*Random Structures & Algorithms*, vol. 47, no. 4, pp. 731-759. https://doi.org/10.1002/rsa.20560

**Randomly coloring planar graphs with fewer colors than the maximum degree.** / Hayes, T.P.; Vera Lizcano, J.C.; Vigoda, E.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - Randomly coloring planar graphs with fewer colors than the maximum degree

AU - Hayes, T.P.

AU - Vera Lizcano, J.C.

AU - Vigoda, E.

PY - 2015/12

Y1 - 2015/12

N2 - 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 k=Ω(Δ/logΔ). 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 Δ^(1-ε), for fixed ε > 0. The main challenge when k≤Δ+1 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 Δ=Ο(1), 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”

AB - 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 k=Ω(Δ/logΔ). 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 Δ^(1-ε), for fixed ε > 0. The main challenge when k≤Δ+1 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 Δ=Ο(1), 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”

KW - Markov chain Monte Carlo

KW - random colorings

KW - approximate counting

KW - Glauber dynamics

KW - mixing time

U2 - 10.1002/rsa.20560

DO - 10.1002/rsa.20560

M3 - Article

VL - 47

SP - 731

EP - 759

JO - Random Structures & Algorithms

JF - Random Structures & Algorithms

SN - 1098-2418

IS - 4

ER -