Perfect Sampling of graph \(k\)-colorings for \(k=o(\Delta^2)\)

Abstract

We give an algorithm for perfect sampling from the uniform distribution on proper \(k\)-colorings of graphs of maximum degree \(\Delta\), which, for \(\Delta \in [17, \log n]\), terminates with a sample in expected time \(\mathrm{poly}(n)\) time whenever \(k >\frac{2e\Delta^2}{\log \Delta}\) (here, \(n\) is the number of vertices in the graph). To the best of our knowledge, this is the first perfect sampling algorithm for proper \(k\)-colorings that provably terminates in expected polynomial time while requiring only \(k=o(\Delta^2)\) colors in general. Inspired by the \emph{bounding chain} approach pioneered independently by H\"aggstr\"om \& Nelander~(Scand. J. Statist., 1999) and Huber~(STOC 1998) (who used the approach to give a perfect sampling algorithm requiring \(k >\Delta^2 + 2\Delta\) for its expected running time to be a polynomial), our algorithm is based on a novel bounding chain for the coloring problem.