Random sampling of colourings of sparse random graphs with a constant number of colours
DOI10.1016/J.TCS.2008.05.008zbMATH Open1152.68043OpenAlexW2057836133MaRDI QIDQ954987FDOQ954987
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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random generation of combinatorial structures from a uniform distribution
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The Complexity of Enumeration and Reliability Problems
- Counting independent sets up to the tree threshold
- Randomly coloring sparse random graphs with fewer colors than the 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
- The two possible values of the chromatic number of a random graph
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
- Counting good truth assignments of random \(k\)-SAT formulae
Cited In (11)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Algorithms to approximately count and sample conforming colorings of graphs
- Minimizing unsatisfaction in colourful neighbourhoods
- Maximum Weight Partial Colorings on Sparse Random Graphs
- Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings
- Title not available (Why is that?)
- A new approach to the vertex coloring problem
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
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)
