Randomly coloring random graphs

DOI10.1002/rsa.20286zbMath1209.05079OpenAlexW1946058994WikidataQ56323832 ScholiaQ56323832MaRDI QIDQ3055885

Martin Dyer, Alan M. Frieze

Publication date: 10 November 2010

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

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

zbMATH Keywords

random graphsGlauber dynamicsrandom coloringsMarkov chain algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On Sampling Simple Paths in Planar Graphs According to Their Lengths, Unnamed Item, Local convergence of random graph colorings

Cites Work

• Unnamed Item
• Path coupling without contraction
• Improved bounds for sampling colorings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Randomly coloring graphs with lower bounds on girth and maximum degree
• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Probability Inequalities for Sums of Bounded Random Variables