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