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

We present a new algorithm for the exact uniform sampling of proper $k$-colorings of a graph on $n$ vertices with maximum degree~$\mathrm{\Delta }$. The algorithm is based on partial rejection sampling (PRS) and introduces a soft relaxation of the proper coloring constraint that is progressively tightened until an exact sample is obtained. Unlike coupling from the past (CFTP), the method is inherently parallelizable. We propose a hybrid variant that decomposes the global sampling problem into independent subproblems of size $O(\log n)$, each solved by any existing exact sampler. This decomposition acts as a {\em complexity reducer}: it replaces the input size~$n$ with $O(\log n)$ in the component solver’s runtime, so that any improvement in direct methods automatically yields a stronger result. Using an existing CFTP method as the component solver, this improves upon the best known exact sampling runtime for $k>3\mathrm{\Delta }$. Recursive application of the hybrid drives the runtime to $O(L^{{\log }^{\ast }n}\cdot n\mathrm{\Delta })$, where $L$ is the number of relaxation levels. We conjecture that $L$ is bounded independently of~$n$, which would yield a linear-time parallelizable algorithm for general graphs. Our simulations strongly support this conjecture.