Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

DOI10.1002/rsa.10020zbMath1002.05023OpenAlexW2117032256WikidataQ56324015 ScholiaQ56324015MaRDI QIDQ4534221

Martin Dyer, Catherine Greenhill, Mike Molloy

Publication date: 9 October 2002

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10020

Mathematics Subject Classification ID

Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Faster mixing and small bottlenecks ⋮ Scaling and universality in continuous length combinatorial optimization ⋮ Approximate Counting via Correlation Decay in Spin Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Logarithmic Sobolev inequalities for finite Markov chains
• An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings
• Improved bounds for sampling colorings
• A more rapidly mixing Markov chain for graph colorings
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph

This page was built for publication: Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs