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 (82)
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
This page was built for publication: A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
