Random sampling of colourings of sparse random graphs with a constant number of colours
| dc.creator | Efthymiou, Charilaos | |
| dc.creator | Spirakis, Paul G. | |
| dc.date | 2008-04-15 | |
| dc.date.accessioned | 2026-07-07T09:46:32Z | |
| dc.date.available | 2026-07-07T09:46:32Z | |
| dc.description | 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. | |
| dc.description | 30 pages 0 figures, uses fullpage.sty | |
| dc.identifier | https://arxiv.org/abs/0804.2343 | |
| dc.identifier | http://arxiv.org/abs/0804.2343 | |
| dc.identifier | doi:10.1016/j.tcs.2008.05.008 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/163564 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | G.3; G.2.1; G.2.2 | |
| dc.title | Random sampling of colourings of sparse random graphs with a constant number of colours | |
| dc.type | text |