  By a theorem of Johansson, every triangle-free graph $G$ of maximum degree
$\Delta$ has chromatic number at most $(C+o(1))\Delta/\log \Delta$ for some
universal constant $C > 0$. Using the entropy compression method, Molloy proved
that one can in fact take $C = 1$. Here we show that for every $q \geq (1 +
o(1))\Delta/\log \Delta$, the number $c(G,q)$ of proper $q$-colorings of $G$
satisfies $c(G, q) \,\geq\, \left(1 - \frac{1}{q}\right)^m ((1-o(1))q)^n$,
where $n = |V(G)|$ and $m = |E(G)|$. Except for the $o(1)$ term, this lower
bound is best possible as witnessed by random $\Delta$-regular graphs. When $q
= (1 + o(1)) \Delta/\log \Delta$, our result yields the inequality $c(G,q)
\,\geq\, \exp\left((1 - o(1)) \frac{\log \Delta}{2} n\right)$, which improves
an earlier bound of Iliopoulos and yields the optimal value for the constant
factor in the exponent. Furthermore, this result implies the optimal lower
bound on the number of independent sets in $G$ due to Davies, Jenssen, Perkins,
and Roberts. An important ingredient in our proof is the counting method that
was recently developed by Rosenfeld. As a byproduct, we obtain an alternative
proof of Molloy's bound $\chi(G) \leq (1 + o(1))\Delta/\log \Delta$ using
Rosenfeld's method in place of entropy compression (other proofs of Molloy's
theorem using Rosenfeld's technique were given independently by Hurley and
Pirot and Martinsson).
