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

DOI10.1016/J.TCS.2008.05.008MaRDI QIDQ954987zbMATHOpenAlexFDO

Authors Charilaos Efthymiou, P. 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Sampling random colorings of sparse random graphs
• A simple algorithm for random colouring \(G(n, d/n)\) using \((2 + \epsilon)d\) colours
• scientific article; zbMATH DE number 5279368
• Algorithms for Colouring Random k-colourable Graphs

Cites work

• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Counting good truth assignments of random \(k\)-SAT formulae
• Counting independent sets up to the tree threshold
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Random generation of combinatorial structures from a uniform distribution
• 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
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The two possible values of the chromatic number of a random graph

Cited in

(12)

• A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
• scientific article; zbMATH DE number 1775385 (Why is no real title available?)
• A new approach to the vertex coloring problem
• Minimizing unsatisfaction in colourful neighbourhoods
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Maximum Weight Partial Colorings on Sparse Random Graphs
• scientific article; zbMATH DE number 5279368 (Why is no real title available?)
• Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings
• Sampling in Potts model on sparse random graphs
• A simple algorithm for random colouring \(G(n, d/n)\) using \((2 + \epsilon)d\) colours
• Algorithms to approximately count and sample conforming colorings of graphs

This page was built for publication: Random sampling of colourings of sparse random graphs with a constant number of colours

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q954987)