Randomly coloring planar graphs with fewer colors than the maximum degree

280 views · Published 8 September 2016 · 51:18 · Indexed 8 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

We study Markov chains for randomly sampling k-colorings of a graph with maximum degree D.  We prove the first results, for a general class of graphs, showing fast convergence of such chains when the number of colors k << D.    When D =O((log n)^(1+eps)) and k > D/log D we prove O(n log n) mixing time of the single-site update chain, known as the Glauber dynamics, for any planar graph.  This result is tight, there exist planar graphs for which the Glauber dynamics has super-polynomial mixing time whenever k = o(D/ log D).    A challenging aspect of the case when D is constant and k < D is that, even in a random coloring, a constant fraction of the vertices are “frozen,” with a unique color not present among its neighbors.  To extend our results to this setting, we introduce a new Markov chain which recolors vertices in a partially deterministic order defined in terms of the principal eigenvector of the graph. For this chain we prove nearly-linear time convergence when k > D/ log D.  This implies polynomial mixing time of the original Glauber dynamics under the same conditions.    Joint work with Thomas P. Hayes and Eric Vigoda.

More from this channel