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



Efthymiou, Charilaos and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2008) Random sampling of colourings of sparse random graphs with a constant number of colours. Theoretical Computer Science, 407 (1-3). pp. 134-154.

[img] Text
0804.2343v1.pdf - Unspecified

Download (370kB)

Abstract

In this work we present a simple and efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper k-colourings on an instance of a sparse random graph G(n,d/n), where k=k(d) is a sufficiently large constant. Our algorithm is not based on the Markov Chain Monte Carlo method (M.C.M.C.). Instead, we provide a novel proof of correctness of our Algorithm that is based on interesting "spatial mixing" properties of colourings of G(n,d/n). Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.

Item Type: Article
Additional Information: 30 pages 0 figures, uses fullpage.sty
Uncontrolled Keywords: cs.DM, cs.DM, G.3; G.2.1; G.2.2
Depositing User: Symplectic Admin
Date Deposited: 08 Apr 2016 11:11
Last Modified: 18 Mar 2024 01:37
DOI: 10.1016/j.tcs.2008.05.008
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3000318