  The problem of sampling proper $q$-colorings from uniform distribution has
been extensively studied. Most of existing samplers require $q\ge \alpha
\Delta+\beta$ for some constants $\alpha$ and $\beta$, where $\Delta$ is the
maximum degree of the graph. The problem becomes more challenging when the
underlying graph has unbounded degree since even the decision of
$q$-colorability becomes nontrivial in this situation. The Erd\H{o}s-R\'{e}nyi
random graph $\mathcal{G}(n,d/n)$ is a typical class of such graphs and has
received a lot of recent attention. In this case, the performance of a sampler
is usually measured by the relation between $q$ and the average degree $d$. We
are interested in the fully polynomial-time almost uniform sampler (FPAUS) and
the state-of-the-art with such sampler for proper $q$-coloring on
$\mathcal{G}(n,d/n)$ requires that $q\ge 5.5d$.
  In this paper, we design an FPAUS for proper $q$-colorings on
$\mathcal{G}(n,d/n)$ by requiring that $q\ge 3d+O(1)$, which improves the best
bound for the problem so far. Our sampler is based on the spatial mixing
property of $q$-coloring on random graphs. The core of the sampler is a
deterministic algorithm to estimate the marginal probability on blocks, which
is computed by a novel block version of recursion for $q$-coloring on unbounded
degree graphs.
