Random sampling of colourings of sparse random graphs with a constant number of colours

DOI10.1016/j.tcs.2008.05.008zbMath1152.68043OpenAlexW2057836133MaRDI QIDQ954987

Charilaos Efthymiou, Paul G. Spirakis

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.05.008

zbMATH Keywords

spin systemsampling colouringssparse random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A NEW APPROACH TO THE VERTEX COLORING PROBLEM, Unnamed Item

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Counting independent sets up to the tree threshold
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• The Complexity of Enumeration and Reliability Problems
• 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
• The two possible values of the chromatic number of a random graph
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item