  Approximate random $k$-colouring of a graph $G$ is a well studied problem in
computer science and statistical physics. It amounts to constructing a
$k$-colouring of $G$ which is distributed close to {\em Gibbs distribution} in
polynomial time. Here, we deal with the problem when the underlying graph is an
instance of Erd\H{o}s-R\'enyi random graph $G(n,d/n)$, where $d$ is a
sufficiently large constant.
  We propose a novel efficient algorithm for approximate random $k$-colouring
$G(n,d/n)$ for any $k\geq (1+\epsilon)d$. To be more specific, with probability
at least $1-n^{-\Omega(1)}$ over the input instances $G(n,d/n)$ and for $k\geq
(1+\epsilon)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 instance.
  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 "simple graph" which can be $k$-coloured randomly efficiently. The
algorithm colours randomly this simple graph. Then it puts back the removed
edges one by one. Every time a new edge is put back the algorithm updates the
colouring of the graph so that the colouring remains random.
  The performance of the algorithm depends heavily on certain spatial
correlation decay properties of the Gibbs distribution.
