## Counting colorings of triangle-free graphs

- Oct. 22, 2021
- 2:30 p.m.

## Abstract

According to a celebrated theorem of Johansson, every triangle-free graph $G$ of maximum degree $\Delta$ has chromatic number $O(\Delta/\log\Delta)$. Molloy recently improved this upper bound to $(1+o(1))\Delta/\log\Delta$. In this talk, we will strengthen Molloyâ€™s result by establishing an optimal lower bound on the number of proper $q$-colorings of $G$ when $q$ is at least $(1+o(1))\Delta/\log\Delta$. One of the main ingredients in our argument is a novel proof technique introduced by Rosenfeld. This is joint work with Tyler Brazelton, Ruijia Cao, and Akum Kang.