On Approximately Counting Colorings of Small Degree Graphs

DOI10.1137/S0097539798338175MaRDI QIDQ4268888zbMATH OpenFDO

Authors Russ Bubley, Martin Dyer, Catherine Greenhill, Mark Jerrum

Publication date 28 October 1999

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

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

zbMATH Keywords

approximate countinggraph coloringsrapidly mixing Markov chainstransportation problems

Mathematics Subject Classification ID

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

Recommendations

• A more rapidly mixing Markov chain for graph colorings
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• scientific article; zbMATH DE number 1775385
• Randomly coloring constant degree graphs

Cited in

(22)

• The complexity of the \(T\)-coloring problem for graphs with small degree
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Counting \(H-\)colorings of partial \(k-\)trees
• Some observations on holographic algorithms
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Star colouring of bounded degree graphs and regular graphs
• The complexity of counting edge colorings for simple graphs
• Counting Candy Crush configurations
• Sampling colourings of the triangular lattice
• Algorithms to approximately count and sample conforming colorings of graphs
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• scientific article; zbMATH DE number 1775385 (Why is no real title available?)
• An FPTAS for counting proper four-colorings on cubic graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• scientific article; zbMATH DE number 764415 (Why is no real title available?)
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• An efficient format-preserving encryption mode for practical domains
• Rapid mixing for lattice colourings with fewer colours
• Counting hypergraph colourings in the local lemma regime
• Counting hypergraph colorings in the local lemma regime
• Perturbation analysis of Markov chain Monte Carlo for graphical models
• Towards a dichotomy theorem for the counting constraint satisfaction problem

This page was built for publication: On Approximately Counting Colorings of Small Degree Graphs

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