Approximate random k-colouring of a graph G=(V,E) is a very well studied problem in computer science, discrete mathematics and statistical physics. It amounts to constructing a k-colouring of G which is distributed close to Gibbs distribution in polynomial time. In this talk, we deal with the problem when the underlying graph is an instance of Erdos-Renyi random graph G(n,d/n), where d is fixed. In this paper we propose a novel efficient algorithm for approximate random k-colouring G(n,d/n). To be more specific, with probability at least 1-n^{-Omega(1)} over the input instances G(n,d/n) and for kgeq (1+eps)d, the algorithm returns a k-colouring which is distributed within total variation distance n^{-Omega(1)} from the Gibbs distribution of the input graph. The algorithm we propose is neither a MCMC one nor inspired by the message passing algorithms proposed by statistical physicists. Roughly the idea is as follows: Initially we remove sufficiently many edges of the input graph. This results in a graph which can be coloured randomly efficiently. Then we move back the removed edges one by one. Every time we add an edge we update the colouring of the graph, with the new edge, so that the colouring remains (sufficiently) random. The performance depends heavily on certain spatial correlation decay properties of the Gibbs distribution.