A simple algorithm for random colouring G(n, d/n) using (2+ε)d colours

Charilaos Efthymiou

Approximate random k-colouring of a graph G=(V,E) is a very well studied problem in computer science and statistical physics. It amounts to constructing a k-colouring of G which is…