Randomly coloring planar graphs with fewer colors than the maximum degree

T.P. Hayes, J.C. Vera Lizcano, E. Vigoda

Research output: Contribution to journalArticleScientificpeer-review

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 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”
Original languageEnglish
Pages (from-to)731-759
JournalRandom Structures & Algorithms
Volume47
Issue number4
Early online date1 Jul 2014
DOIs
Publication statusPublished - Dec 2015

Fingerprint

Mixing Time
Coloring
Maximum Degree
Planar graph
Colouring
Color
Glauber Dynamics
Adjacency Matrix
Graph in graph theory
Uniformity
Markov processes
Markov chain
Update
Polynomials
Sampling
Upper bound
Eigenvalue
Polynomial

Keywords

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

Cite this

@article{6050932dee58479c835fdd7394f187d2,
title = "Randomly coloring planar graphs with fewer colors than the maximum degree",
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 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”",
keywords = "Markov chain Monte Carlo, random colorings, approximate counting, Glauber dynamics, mixing time",
author = "T.P. Hayes and {Vera Lizcano}, J.C. and E. Vigoda",
year = "2015",
month = "12",
doi = "10.1002/rsa.20560",
language = "English",
volume = "47",
pages = "731--759",
journal = "Random Structures & Algorithms",
issn = "1098-2418",
publisher = "John Wiley and Sons Ltd",
number = "4",

}

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

In: Random Structures & Algorithms, Vol. 47, No. 4, 12.2015, p. 731-759.

Research output: Contribution to journalArticleScientificpeer-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 -