Algorithms to approximately count and sample conforming colorings of graphs

DOI10.1016/J.DAM.2015.05.003MaRDI QIDQ299070zbMATH OpenOpenAlexFDO

Authors Sarah Miracle, Dana Randall

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

\(H\)-coloringsadapted coloringsindependent setsMarkov chains

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1775385
• On Approximately Counting Colorings of Small Degree Graphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Improved bounds for sampling colorings
• Random sampling of colourings of sparse random graphs with a constant number of colours

Cites work

• A more rapidly mixing Markov chain for graph colorings
• A survey on the use of Markov chains to randomly sample colourings
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Adaptable chromatic number of graph products
• Adapted List Coloring of Graphs and Hypergraphs
• Adapted list coloring of planar graphs
• Analyzing Glauber dynamics by comparison of Markov chains
• Comparison theorems for reversible Markov chains
• Fast convergence of the Glauber dynamics for sampling independent sets
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 2019624 (Why is no real title available?)
• scientific article; zbMATH DE number 2151247 (Why is no real title available?)
• scientific article; zbMATH DE number 1445311 (Why is no real title available?)
• Improved bounds for sampling colorings
• On Markov chains for randomly H-coloring a graph
• On the adaptable chromatic number of graphs
• On the complexity of H-coloring
• Phase coexistence and slow mixing for the hard-core model on \(\mathbb Z^{2}\)
• Random generation of combinatorial structures from a uniform distribution
• The adaptable choosability number grows with the choosability number
• The Complexity of the List Partition Problem for Graphs
• The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem

Cited in

(2)

• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold

This page was built for publication: Algorithms to approximately count and sample conforming colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299070)