Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
Sarat Moka, Ava Vahedi · 2026
Read Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling by Sarat Moka, Ava Vahedi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03947.txt.
Description
Sarat Moka and Ava Vahedi gave a new algorithm for exact uniform sampling of proper graph colorings. Their method softens the coloring rule and tightens it step by step under partial rejection sampling, unlike coupling from the past, and it runs in parallel naturally. A hybrid variant splits the task into independent chunks of size log n, each handled by any exact sampler. Using coupling from the past inside, it beat the best known runtime for k greater than 3 Delta, with simulations backing a linear-time conjecture.
Catalog record
| CREATOR | Sarat Moka, Ava Vahedi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81189 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.03947