{"id":"arxiv/2604.03947","url":"https://arxiv.org/abs/2604.03947","tags":["cs.DS","cs.CC","math.PR"],"score":0,"title":"Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling","domain":"cs.DS","source":"arxiv","authors":["Sarat Moka","Ava Vahedi"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-05","reactions":{}}