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

Charilaos Efthymiou, Paul G. Spirakis

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 spa…