Deterministic counting of graph colourings using sequences of subgraphs
From MaRDI portal
Publication:4993106
DOI10.1017/S0963548320000255zbMath1504.68163MaRDI QIDQ4993106
Publication date: 15 June 2021
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Local convergence of random graph colorings
- Random generation of combinatorial structures from a uniform distribution
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Improved mixing condition on the grid for counting and sampling independent sets
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Improved bounds for sampling colorings
- Counting independent sets up to the tree threshold
- Rapid mixing of Gibbs sampling on graphs that are sparse on average
- Graphical Models, Exponential Families, and Variational Inference
- Information, Physics, and Computation
- Almost all regular graphs are hamiltonian
- Sampling Random Colorings of Sparse Random Graphs
- Sampling in Potts Model on Sparse Random Graphs
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
- Planting Colourings Silently
- Gibbs states and the set of solutions of random constraint satisfaction problems
- A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
- The condensation phase transition in random graph coloring
This page was built for publication: Deterministic counting of graph colourings using sequences of subgraphs