2015/03/11 by Yitong Yin, Yin, Yitong, Chihao Zhang +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1503.03351
openalex publication_date 2015/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of sampling proper q-colorings from uniform distribution has been extensively studied. Most of existing samplers require q≥ αΔ+β for some constants α and β, where Δ is the maximum degree of the graph. The problem becomes more challenging when the underlying graph has unbounded degree since even the decision of q-colorability becomes nontrivial in this situation. The Erdős-Rényi random graph G(n,d/n) is a typical class of such graphs and has received a lot of recent attention. In this case, the performance of a sampler is usually measured by the relation between q and the average degree d. We are interested in the fully polynomial-time almost uniform sampler (FPAUS) and the state-of-the-art with such sampler for proper q-coloring on G(n,d/n) requires that q≥ 5.5d. In this paper, we design an FPAUS for proper q-colorings on G(n,d/n) by requiring that q≥ 3d+O(1), which improves the best bound for the problem so far. Our sampler is based on the spatial mixing property of q-coloring on random graphs. The core of the sampler is a deterministic algorithm to estimate the marginal probability on blocks, which is computed by a novel block version of recursion for q-coloring on unbounded degree graphs.