Randomly coloring graphs of bounded treewidth

Abstract

We consider the problem of sampling a proper $k$-coloring of a graph of maximal degree $\Delta$ uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of bounded treewidth if $k\ge (1+\epsilon )\Delta$, for any $\epsilon >0$.

References in corpus (1)

• An FPTAS for Counting Proper Four-Colorings on Cubic Graphs