Randomly coloring planar graphs with fewer colors than the maximum degree1. Issue 4 (1st July 2014) - Hayes, Thomas P.; Vera, Juan C.; Vigoda, Eric
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk854" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k=Ω(Δ/logΔ)</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk833" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Δ1−ϵ</alternatives>, for fixed <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk8f8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ϵ>0</alternatives>. The main challenge when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk8dr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k≤Δ+1</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvk8c7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Δ=O(1)</alternatives>, 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