Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

DOI10.1137/20M1366666zbMath1482.05096OpenAlexW2988940459MaRDI QIDQ5026395

Sayantan Chakraborty, Siddharth Bhandari

Publication date: 8 February 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1366666

zbMATH Keywords

Markov chainscoupling from the pastgraph coloringsperfect/exact sampling

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Combinatorics and complexity of partition functions
• Random generation of combinatorial structures from a uniform distribution
• Some simplified NP-complete graph problems
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• Perfect sampling using bounding chains.
• Improved bounds for sampling colorings
• Improved FPTAS for Multi-spin Systems
• Randomly coloring constant degree graphs
• Randomly coloring planar graphs with fewer colors than the maximum degree
• A constructive proof of the general lovász local lemma
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• On Exact Simulation of Markov Random Fields Using Coupling from the Past
• Improved bounds for perfect sampling of k-colorings in graphs
• Improved Bounds for Randomly Sampling Colorings via Linear Programming
• Uniform Sampling Through the Lovász Local Lemma