  We revisit the complexity of the classical $k$-Coloring problem parameterized
by clique-width. This is a very well-studied problem that becomes highly
intractable when the number of colors $k$ is large. However, much less is known
on its complexity for small, concrete values of $k$. In this paper, we
completely determine the complexity of $k$-Coloring parameterized by
clique-width for any fixed $k$, under the SETH. Specifically, we show that for
all $k\ge 3,\epsilon>0$, $k$-Coloring cannot be solved in time
$O^*((2^k-2-\epsilon)^{cw})$, and give an algorithm running in time
$O^*((2^k-2)^{cw})$. Thus, if the SETH is true, $2^k-2$ is the "correct" base
of the exponent for every $k$.
  Along the way, we also consider the complexity of $k$-Coloring parameterized
by the related parameter modular treewidth ($mtw$). In this case we show that
the "correct" running time, under the SETH, is $O^*({k\choose \lfloor
k/2\rfloor}^{mtw})$. If we base our results on a weaker assumption (the ETH),
they imply that $k$-Coloring cannot be solved in time $n^{o(cw)}$, even on
instances with $O(\log n)$ colors.
