On Approximately Counting Colorings of Small Degree Graphs

DOI10.1137/S0097539798338175zbMath0937.05041MaRDI QIDQ4268888

Catherine Greenhill, Russ Bubley, Martin Dyer, Mark R. Jerrum

Publication date: 28 October 1999

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

zbMATH Keywords

transportation problemsapproximate countinggraph coloringsrapidly mixing Markov chains

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Number-theoretic algorithms; complexity (11Y16) Coloring of graphs and hypergraphs (05C15)

Related Items

Some observations on holographic algorithms ⋮ Star colouring of bounded degree graphs and regular graphs ⋮ Sampling colourings of the triangular lattice ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ An efficient format-preserving encryption mode for practical domains ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ Rapid mixing for lattice colourings with fewer colours ⋮ Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z² ⋮ Counting \(H-\)colorings of partial \(k-\)trees