  This paper studies sufficient conditions to obtain efficient distributed
algorithms coloring graphs optimally (i.e.\ with the minimum number of colors)
in the LOCAL model of computation. Most of the work on distributed vertex
coloring so far has focused on coloring graphs of maximum degree $\Delta$ with
at most $\Delta+1$ colors (or $\Delta$ colors when some simple obstructions are
forbidden). When $\Delta$ is sufficiently large and $c\ge \Delta-k_\Delta+1$,
for some integer $k_\Delta\approx \sqrt{\Delta}-2$, we give a distributed
algorithm that given a $c$-colorable graph $G$ of maximum degree $\Delta$,
finds a $c$-coloring of $G$ in $\min\{O((\log\Delta)^{1/12}\log n), 2^{O(\log
\Delta+\sqrt{\log \log n})}\}$ rounds, with high probability. The lower bound
$\Delta-k_\Delta+1$ is best possible in the sense that for infinitely many
values of $\Delta$, we prove that when $\chi(G)\le \Delta -k_\Delta$, finding
an optimal coloring of $G$ requires $\Omega(n)$ rounds. Our proof is a light
adaptation of a remarkable result of Molloy and Reed, who proved that for
$\Delta$ large enough, for any $c\ge \Delta - k_\Delta$ deciding whether
$\chi(G)\le c$ is in {\textsf{P}}, while Embden-Weinert \emph{et al.}\ proved
that for $c\le \Delta-k_\Delta-1$, the same problem is {\textsf{NP}}-complete.
Note that the sequential and distributed thresholds differ by one. We also show
that for any sufficiently large $\Delta$, and $\Omega(\log \Delta)\le k \le
\Delta/100$, every graph of maximum degree $\Delta$ and clique number at most
$\Delta-k$ can be efficiently colored with at most $\Delta-\varepsilon k$
colors, for some absolute constant $\varepsilon >0$, with a randomized
algorithm running in $O(\log n/\log \log n)$ rounds with high probability.
