A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
From MaRDI portal
Publication:4847401
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
Cites work
- scientific article; zbMATH DE number 822898 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- Decay of correlations in classical lattice models at high temperature
- Random generation of combinatorial structures from a uniform distribution
- Some simplified NP-complete graph problems
Cited in
(84)- Sampling colourings of the triangular lattice
- A faster FPTAS for counting two-rowed contingency tables
- Reconfiguring vertex colourings of 2-trees
- Counting hypergraph colorings in the local lemma regime
- Paths between colourings of graphs with bounded tree-width
- Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs
- Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs
- scientific article; zbMATH DE number 7561278 (Why is no real title available?)
- 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
- Counting and sampling \(H\)-colourings
- Classifying coloring graphs
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Paths between colourings of sparse graphs
- H-coloring tori
- Sampling random graph homomorphisms and applications to network data analysis
- Frozen \((\Delta+1)\)-colourings of bounded degree graphs
- 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
- Secret-sharing schemes for very dense graphs
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
- Some problems on approximate counting in graphs and matroids
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Algorithms to approximately count and sample conforming colorings of graphs
- Random sampling of colourings of sparse random graphs with a constant number of colours
- Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2
- Perfect sampling from spatial mixing
- Mixing 3-colourings in bipartite graphs
- Systematic scan for sampling colorings
- Randomly coloring simple hypergraphs with fewer colors
- On mixing of Markov chains: coupling, spectral independence, and entropy factorization
- Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration
- 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
- Optimally reconfiguring list and correspondence colourings
- Rapid mixing of Gibbs sampling on graphs that are sparse on average
- Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
- scientific article; zbMATH DE number 1563189 (Why is no real title available?)
- Approximate counting via correlation decay in spin systems
- An update on reconfiguring 10-colorings of planar graphs
- Forests, colorings and acyclic orientations of the square lattice
- Improved bounds for perfect sampling of \(k\)-colorings in graphs
- Frozen colourings of bounded degree graphs
- Rapid mixing for lattice colourings with fewer colours
- Counting \(H-\)colorings of partial \(k-\)trees
- Dynamic Sampling from Graphical Models
- Average mixing in quantum walks of reversible Markov chains
- On reconfiguration graphs: an abstraction
- An FPTAS for the hardcore model on random regular bipartite graphs
- Spectral independence, coupling, and the spectral gap of the Glauber dynamics
- Local uniformity properties for Glauber dynamics on graph colorings
- 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
- Recoloring graphs via tree decompositions
- Matrix norms and rapid mixing for spin systems
- Distributed recoloring
- The Markov chain of colourings
- Randomly coloring constant degree graphs
- Recoloring some hereditary graph classes
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Glauber dynamics on trees and hyperbolic graphs
- On systematic scan for sampling \(H\)-colorings of the path
- Improved bounds for sampling colorings
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Path coupling without contraction
- Randomly coloring simple hypergraphs
- The Glauber dynamics for edge-colorings of trees
- Finding paths between 3-colorings
- What can be sampled locally?
- Randomly coloring graphs of logarithmically bounded pathwidth
- A note on graphs of \(k\)-colourings
- Cutoff for conjugacy-invariant random walks on the permutation group
- Analyzing Glauber dynamics by comparison of Markov chains
- Radiocoloring in planar graphs: Complexity and approximations
- Randomly coloring random graphs
- Logarithmic Sobolev inequalities for finite spin systems and applications
- Very rapidly mixing Markov chains for \(2\Delta\)-colorings and for independent sets in a graph with maximum degree 4
- Reconfiguration graphs of zero forcing sets
- Strong spatial mixing and rapid mixing with five colours for the Kagome 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)
