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~\(Δ\). 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.03947
curl -X POST /api/v1/records/arxiv/2604.03947/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.03947/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'