On Approximately Counting Colorings of Small Degree Graphs

Russ Bubley, Martin Dyer, Catherine Greenhill, Mark Jerrum

Type: Article

Publication Date: 1999-01-01

Citations: 49

DOI: https://doi.org/10.1137/s0097539798338175

View Publication

Locations

SIAM Journal on Computing - View

Similar Works

Action	Title	Year	Authors
+	Randomly coloring graphs of bounded treewidth	2017	Shai Vardi
+	Path Coupling Using Stopping Times	2005	Magnus Bordewich Martin Dyer Marek Karpiński
+	Linear Programming Bounds for Randomly Sampling Colorings	2018	Sitan Chen Ankur Moitra
+	Rapid Mixing for Colorings via Spectral Independence	2020	Zongchen Chen Andreas Galanis Daniel Štefankovič Eric Vigoda
+ PDF Chat	Coupling with the stationary distribution and improved sampling for colorings and independent sets	2006	Thomas P. Hayes Eric Vigoda
+ PDF Chat	Systematic scan for sampling colorings	2006	Martin Dyer Leslie Ann Goldberg Mark Jerrum
+	Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs	2005	Magnus Bordewich Martin Dyer Marek Karpiński
+	Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs	2005	Magnus Bordewich Martin Dyer Marek Karpiński
+ PDF Chat	Approximation via Correlation Decay When Strong Spatial Mixing Fails	2019	Ivona Bezáková Andreas Galanis Leslie Ann Goldberg Heng Guo Daniel Štefankovič
+	Randomly coloring simple hypergraphs with fewer colors	2017	Michael Anastos Alan Frieze
+	Randomly coloring simple hypergraphs with fewer colors	2017	Michael Anastos Alan Frieze
+ PDF Chat	Rapid Mixing for Colorings via Spectral Independence	2021	Zongchen Chen Andreas Galanis Daniel Štefankovič Eric Vigoda
+	Coupling with the stationary distribution and improved sampling for colorings and independent sets	2005	Tom Hayes Eric Vigoda
+	An FPTAS for Counting Proper Four-Colorings on Cubic Graphs	2016	Pinyan Lu Kuan Yang Chihao Zhang Minshen Zhu
+	A survey on the use of Markov chains to randomly sample colorings	2006	Alan Frieze Eric Vigoda
+	A non-Markovian coupling for randomly sampling colorings	2004	Thomas P. Hayes Eric Vigoda
+	Approximation via Correlation Decay when Strong Spatial Mixing Fails	2015	Ivona Bezáková Andreas Galanis Leslie Ann Goldberg Heng Guo Daniel Štefankovič
+	Exact and approximate counting of graph objects: independent sets, eulerian tours, and more	2011	Daniel Štefankovič Qi Ge
+	Correlation decay and deterministic FPTAS for counting list-colorings of a graph	2006	David Gamarnik Dmitriy Katz
+	Counting without sampling	2006	Antar Bandyopadhyay David Gamarnik

Works That Cite This (38)

Action	Title	Year	Authors
+ PDF Chat	Zero-Free Regions of Partition Functions with Applications to Algorithms and Graph Limits	2017	Guus Regts
+ PDF Chat	Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials	2017	Viresh Patel Guus Regts
+ PDF Chat	Approximate Counting of Matchings in Sparse Uniform Hypergraphs	2013	Marek Karpiński Andrzej Ruciński Edyta Szymańska
+ PDF Chat	Star colouring of bounded degree graphs and regular graphs	2022	M. A. Shalu Cyriac Antony
+	Sampling on lattices with free boundary conditions using randomized extensions	2016	Sarah Cannon Dana Randall
+	The complexity of counting graph homomorphisms	2000	Martin Dyer Catherine Greenhill
+	Towards a dichotomy theorem for the counting constraint satisfaction problem	2006	Andreĭ A. Bulatov Víctor Dalmau
+	Counting H-colorings of partial k-trees	2002	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Strong Spatial Mixing with Fewer Colors for Lattice Graphs	2005	Leslie Ann Goldberg Russell Martin Mike Paterson
+	An introduction to computational complexity in Markov Chain Monte Carlo methods	2020	Izhar Asael Alonzo Matamoros

Works Cited by This (13)

Action	Title	Year	Authors
+	The Markov chain Monte Carlo method: an approach to approximate counting and integration	1996	Mark Jerrum Alistair Sinclair
+	On Markov Chains for Independent Sets	2000	Martin Dyer Catherine Greenhill
+ PDF Chat	Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem	1997	Jesús Salas Alan D. Sokal
+ PDF Chat	A modified heat bath method suitable for Monte Carlo simulations on vector and parallel processors	1987	Klaus Fredenhagen Marius Marcu
+	On the computational complexity of the Jones and Tutte polynomials	1990	François Jaeger Dirk Vertigan Dominic Welsh
+	A more rapidly mixing Markov chain for graph colorings	1998	Martin Dyer Catherine Greenhill
+ PDF Chat	A random polynomial-time algorithm for approximating the volume of convex bodies	1991	Martin Dyer Alan Frieze Ravi Kannan
+ PDF Chat	Approximating the Permanent	1989	Mark Jerrum Alistair Sinclair
+	A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph	1995	Mark Jerrum
+ PDF Chat	Path coupling: A technique for proving rapid mixing in Markov chains	2002	Russ Bubley Martin Dyer