A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph

DOI10.1002/RSA.3240070205zbMATH Open0833.60070OpenAlexW2109260999MaRDI QIDQ4847401FDOQ4847401

Authors: Mark Jerrum 

Publication date: 14 March 1996

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240070205

Recommendations

• On Approximately Counting Colorings of Small Degree Graphs
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Improved bounds for sampling colorings
• scientific article; zbMATH DE number 1775385
• A simple algorithm for random colouring \(G(n, d/n)\) using \((2 + \epsilon)d\) colours

zbMATH Keywords

randomized algorithmsstationary distributionproblem of coloring of a graph

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• Decay of correlations in classical lattice models at high temperature
• Title not available (Why is that?)

Cited In (84)

• Counting hypergraph colorings in the local lemma regime
• Title not available (Why is that?)
• Sampling random graph homomorphisms and applications to network data analysis
• Some problems on approximate counting in graphs and matroids
• Randomly coloring simple hypergraphs with fewer colors
• Optimally reconfiguring list and correspondence colourings
• Title not available (Why is that?)
• Average mixing in quantum walks of reversible Markov chains
• Spectral independence, coupling, and the spectral gap of the Glauber dynamics
• Local uniformity properties for Glauber dynamics on graph colorings
• Recoloring some hereditary graph classes
• On systematic scan for sampling \(H\)-colorings of the path
• The Glauber dynamics for edge-colorings of trees
• Randomly coloring graphs of logarithmically bounded pathwidth
• A note on graphs of \(k\)-colourings
• Very rapidly mixing Markov chains for \(2\Delta\)-colorings and for independent sets in a graph with maximum degree 4
• Reconfiguring vertex colourings of 2-trees
• A faster FPTAS for counting two-rowed contingency tables
• Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
• Paths between colourings of graphs with bounded tree-width
• Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs
• Cut-colorings in coloring graphs
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Mixing 3-Colourings in Bipartite Graphs
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Counting and sampling \(H\)-colourings
• Classifying coloring graphs
• Paths between colourings of sparse graphs
• Frozen \((\Delta+1)\)-colourings of bounded degree graphs
• \(H\)-coloring tori
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• Tunneling behavior of Ising and Potts models in the low-temperature regime
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Secret-sharing schemes for very dense graphs
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Algorithms to approximately count and sample conforming colorings of graphs
• Perfect sampling from spatial mixing
• Random sampling of colourings of sparse random graphs with a constant number of colours
• Mixing 3-colourings in bipartite graphs
• Systematic scan for sampling colorings
• Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration
• On mixing of Markov chains: coupling, spectral independence, and entropy factorization
• Zero-freeness and approximation of real Boolean Holant problems
• Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
• Introduction to reconfiguration
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• Approximate counting via correlation decay in spin systems
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• An update on reconfiguring 10-colorings of planar graphs
• Improved bounds for perfect sampling of \(k\)-colorings in graphs
• Forests, colorings and acyclic orientations of the square lattice
• Rapid mixing for lattice colourings with fewer colours
• Frozen colourings of bounded degree graphs
• Dynamic Sampling from Graphical Models
• On reconfiguration graphs: an abstraction
• Counting \(H-\)colorings of partial \(k-\)trees
• An FPTAS for the hardcore model on random regular bipartite graphs
• Strong spatial mixing of list coloring of graphs
• A general lower bound for mixing of single-site dynamics on graphs
• Forbidden subgraphs of coloring graphs
• Connectedness of the graph of vertex-colourings
• Distributed recoloring
• The Markov chain of colourings
• Recoloring graphs via tree decompositions
• Matrix norms and rapid mixing for spin systems
• Randomly coloring constant degree graphs
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Glauber dynamics on trees and hyperbolic graphs
• Improved bounds for sampling colorings
• Path coupling without contraction
• Randomly coloring simple hypergraphs
• Finding paths between 3-colorings
• What can be sampled locally?
• Analyzing Glauber dynamics by comparison of Markov chains
• Cutoff for conjugacy-invariant random walks on the permutation group
• Radiocoloring in planar graphs: Complexity and approximations
• Randomly coloring random graphs
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Reconfiguration graphs of zero forcing sets
• Strong spatial mixing and rapid mixing with five colours for the Kagome lattice
• Sampling colourings of the triangular lattice

This page was built for publication: A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph

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