A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
From MaRDI portal
Publication:4847401
DOI10.1002/rsa.3240070205zbMath0833.60070OpenAlexW2109260999MaRDI QIDQ4847401
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
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)
Related Items
Randomly coloring simple hypergraphs with fewer colors, Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration, Paths between colourings of sparse graphs, Classifying coloring graphs, Secret-sharing schemes for very dense graphs, Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs, Counting and sampling \(H\)-colourings, Algorithms to approximately count and sample conforming colorings of graphs, Sampling colourings of the triangular lattice, Zero-freeness and approximation of real Boolean Holant problems, Unnamed Item, Randomly coloring planar graphs with fewer colors than the maximum degree, Mixing of the Glauber dynamics for the ferromagnetic Potts model, Coupling with the stationary distribution and improved sampling for colorings and independent sets, An FPTAS for the hardcore model on random regular bipartite graphs, Logarithmic Sobolev inequalities for finite spin systems and applications, Spectral independence, coupling, and the spectral gap of the Glauber dynamics, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, Forbidden subgraphs of coloring graphs, Recoloring graphs via tree decompositions, The Markov chain of colourings, Perfect sampling from spatial mixing, Optimally reconfiguring list and correspondence colourings, What can be sampled locally?, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, Correlation decay and deterministic FPTAS for counting colorings of a graph, Mixing 3-Colourings in Bipartite Graphs, Reconfiguration graphs of zero forcing sets, Randomly coloring simple hypergraphs, Fixing improper colorings of graphs, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Unnamed Item, Some Problems on Approximate Counting in Graphs and Matroids, Unnamed Item, Paths between colourings of graphs with bounded tree-width, Unnamed Item, An update on reconfiguring 10-colorings of planar graphs, A general lower bound for mixing of single-site dynamics on graphs, Path coupling without contraction, Finding paths between 3-colorings, Cut-colorings in coloring graphs, Cutoff for conjugacy-invariant random walks on the permutation group, A faster FPTAS for counting two-rowed contingency tables, Improved bounds for sampling colorings, Analyzing Glauber dynamics by comparison of Markov chains, Connectedness of the graph of vertex-colourings, Random sampling of colourings of sparse random graphs with a constant number of colours, Tunneling behavior of Ising and Potts models in the low-temperature regime, Systematic scan for sampling colorings, \(H\)-coloring tori, Glauber dynamics on trees and hyperbolic graphs, 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, Unnamed Item, Frozen colourings of bounded degree graphs, Gibbs rapidly samples colorings of \(G(n, d/n)\), Matrix norms and rapid mixing for spin systems, Reconfiguring vertex colourings of 2-trees, Rapid mixing for lattice colourings with fewer colours, The Glauber dynamics for edge‐colorings of trees, Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice, Distributed Recoloring, Counting Hypergraph Colorings in the Local Lemma Regime, Approximate Counting via Correlation Decay in Spin Systems, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, Frozen (Δ + 1)-colourings of bounded degree graphs, Mixing 3-colourings in bipartite graphs, Phase coexistence and torpid mixing in the 3-coloring model on ${\mathbb Z}^d$, Radiocoloring in planar graphs: Complexity and approximations, Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs, Introduction to reconfiguration, Local uniformity properties for glauber dynamics on graph colorings, Randomly coloring constant degree graphs, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2, Dynamic Sampling from Graphical Models, Forests, colorings and acyclic orientations of the square lattice, On mixing of Markov chains: coupling, spectral independence, and entropy factorization, Strong spatial mixing of list coloring of graphs, Counting \(H-\)colorings of partial \(k-\)trees, Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs
Cites Work
