Counting and sampling \(H\)-colourings

DOI10.1016/j.ic.2003.09.001zbMath1082.68079OpenAlexW1977104034WikidataQ56323928 ScholiaQ56323928MaRDI QIDQ1887143

Leslie Ann Goldberg, Martin Dyer, Mark R. Jerrum

Publication date: 23 November 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2003.09.001

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard, The Complexity of Approximately Counting Tree Homomorphisms, Counting hypergraph matchings up to uniqueness threshold, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard, Approximate Counting via Correlation Decay in Spin Systems

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Gibbs measures and dismantlable graphs
• On Markov Chains for Randomly H-Coloring a Graph
• The complexity of choosing an H -colouring (nearly) uniformly at random
• Foundations of Cryptography
• The computational complexity of two‐state spin systems
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item