Colouring random graphs in expected polynomial time

We investigate the problem of colouring random graphs G C G(n,p) in polynomial expected time. For the case p < 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For sufficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(rootnp). As a by-product, we obtain an O(rootnp/ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided P much greater than ln(6) n/n.