Perfect Sampling of graph k -colorings for k > 3 Δ
We give an algorithm for perfect sampling from the uniform distribution on proper k -colorings of graphs of maximum degree Δ which terminates with a sample in expected time poly(k , n) whenever k ≥ 3 Δ (here, n is the number of vertices in the graph).
Inspired by the bounding chain approach pioneered independently by Häggström & Nelander (Scand. J. Statist., 1999) and Huber (STOC 1998) (who used the approach to give a perfect sampling algorithm requiring k > Δ2 + 2Δ 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.