Premium
Randomly coloring planar graphs with fewer colors than the maximum degree
Author(s) -
Hayes Thomas P.,
Vera Juan C.,
Vigoda Eric
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20560
Subject(s) - combinatorics , mathematics , glauber , complete coloring , planar graph , greedy coloring , degree (music) , graph coloring , markov chain , discrete mathematics , fractional coloring , adjacency matrix , graph , graph power , line graph , statistics , physics , acoustics , scattering , optics
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 Δ = O ( 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” properties. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 731–759, 2015