Counting colorings of triangle-free graphs

Anton Bernshteyn, Tyler Brazelton, Ruijia Cao +1

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 entrop…