A simple algorithm for random colouring G(n, d/n) using (2 + )d colours

MaRDI QIDQ5743398zbMATH OpenFDO

Authors Charilaos Efthymiou

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1107.0871, https://dl.acm.org/citation.cfm?id=2095141

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
• Switching colouring of \(G(n,d/n)\) for sampling up to Gibbs uniqueness threshold
• Random sampling of colourings of sparse random graphs with a constant number of colours
• Algorithms for Colouring Random k-colourable Graphs
• scientific article; zbMATH DE number 1962838

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?)
• Counting without sampling
• Factor graphs and the sum-product algorithm
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Gibbs states and the set of solutions of random constraint satisfaction problems
• MCMC sampling colourings and independent sets of \(G(n, d/n)\) near uniqueness threshold
• On colouring random graphs
• Random sampling of colourings of sparse random graphs with a constant number of colours
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Reconstruction and clustering in random constraint satisfaction problems
• Survey propagation: An algorithm for satisfiability
• The two possible values of the chromatic number of a random graph

Cited in

(9)

• Deterministic counting of graph colourings using sequences of subgraphs
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold
• An approximate algorithm for the \( (k,d)\)-coloring problem
• Random sampling of colourings of sparse random graphs with a constant number of colours
• Switching colouring of \(G(n,d/n)\) for sampling up to Gibbs uniqueness threshold
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs

This page was built for publication: A simple algorithm for random colouring \(G(n, d/n)\) using \((2 + \epsilon)d\) colours

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