Algorithms to approximately count and sample conforming colorings of graphs

DOI10.1016/j.dam.2015.05.003zbMath1339.05142OpenAlexW2177704276MaRDI QIDQ299070

Dana Randall, Sarah Miracle

Publication date: 22 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.05.003

zbMATH Keywords

Markov chainsindependent sets\(H\)-coloringsadapted colorings

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The adaptable choosability number grows with the choosability number
• Adaptable chromatic number of graph products
• Random generation of combinatorial structures from a uniform distribution
• On the complexity of H-coloring
• Comparison theorems for reversible Markov chains
• On the adaptable chromatic number of graphs
• On Markov Chains for Randomly H-Coloring a Graph
• Improved bounds for sampling colorings
• Analyzing Glauber dynamics by comparison of Markov chains
• Phase Coexistence and Slow Mixing for the Hard-Core Model on ℤ2
• Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions
• The Complexity of the List Partition Problem for Graphs
• Adapted List Coloring of Graphs and Hypergraphs
• Adapted list coloring of planar graphs
• Fast convergence of the Glauber dynamics for sampling independent sets
• A more rapidly mixing Markov chain for graph colorings
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph