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

zbMATH Open1421.68189arXiv1107.0871MaRDI QIDQ5743398FDOQ5743398

Authors: Charilaos Efthymiou 

Publication date: 10 May 2019

Full work available at URL: https://arxiv.org/abs/1107.0871

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

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)

Cites Work

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

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)