Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling

Sarat Moka, Ava Vahedi

We present a new algorithm for the exact uniform sampling of proper \(k\)-colorings of a graph on \(n\) vertices with maximum degree~\(Δ\). The algorithm is based on partial reject…