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

CREATORSarat Moka, Ava Vahedi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81189
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.03947

Browse the full library · About the Tower of Babel