"Randomly coloring graphs of bounded treewidth"
Shai Vardi (Caltech)
Monday, October 9, 2017, 2:00 pm
EBU3B, Room 4258
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>(1+\epsilon)\Delta$, for any $\epsilon>0$.