Random sampling of colourings of sparse random graphs with a constant number of colours
type: Item
instance of: scholarly article
title: Random sampling of colourings of sparse random graphs with a constant number of colours
zbMATH Open document ID: 1152.68043
author: Charilaos Efthymiou
author: P. G. Spirakis
published in: Theoretical Computer Science
publication date: 2008-11-18T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5368324
zbMATH Keywords: sampling colourings
zbMATH Keywords: sparse random graph
zbMATH Keywords: spin system
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.05.008
OpenAlex ID: W2057836133
cites work: The two possible values of the chromatic number of a random graph
cites work: Q3660628
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Randomly coloring sparse random graphs with fewer colors than the maximum degree
cites work: Q4519896
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
cites work: The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
cites work: Q2934721
cites work: Gibbs rapidly samples colorings of \(G(n, d/n)\)
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Counting independent sets up to the tree threshold
DOI: 10.1016/J.TCS.2008.05.008
description: scientific article; zbMATH DE number 5368324