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

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 sparse random graphs Gn,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 Gn,d/n. Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.