Deterministic counting of graph colourings using sequences of subgraphs

DOI10.1017/S0963548320000255zbMath1504.68163MaRDI QIDQ4993106

Charilaos Efthymiou

Publication date: 15 June 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

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