Counting colorings of triangle-free graphs

Anton Bernshteyn, Tyler Brazelton, Ruijia Cao, Akum Kang

Published 2021-09-27, updated 2022-06-17Version 3

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.