We give an algorithm for perfect sampling from the uniform distribution on proper $k$-colorings of graphs of maximum degree $\Delta$ which terminates with a sample in expected time $\mathrm{poly}(k,n)$ whenever $k\geq 3\Delta$ (here, $n$ is the number of vertices in the graph).

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.

This is joint work with Sayantan Chakraborty at TIFR Mumbai.