Improved bounds for perfect sampling of k-colorings in graphs
share
We present a randomized algorithm that takes as input an undirected n-vertex graph G with maximum degree Δ and an integer k > 3Δ, and returns a random proper k-coloring of G. The distribution of the coloring is perfectly uniform over the set of all proper k-colorings; the expected running time of the algorithm is poly(k,n)=O(nΔ^2·log(k)). This improves upon a result of Huber (STOC 1998) who obtained polynomial time perfect sampling algorithm for k>Δ^2+2Δ. Prior to our work, no algorithm with expected running time poly(k,n) was known to guarantee perfectly sampling for Δ = ω(1) and for any k ≤Δ^2+2Δ. Our algorithm (like several other perfect sampling algorithms including Huber's) is based on the Coupling from the Past method. Inspired by the bounding chain approach pioneered independently by Häggström & Nelander (Scand. J. Statist., 1999) and Huber (STOC 1998), our algorithm is based on a novel bounding chain for the coloring problem.
READ FULL TEXT