Seminar series
Date
Tue, 15 Mar 2022
14:00
14:00
Location
C6
Speaker
Eoin Hurley
Organisation
Heidelberg University
A classical theorem of Molloy and Johansson states that if a graph is triangle free and has maximum degree at most $\Delta$, then it has chromatic number at most $\frac{\Delta}{\log \Delta}$. This was extended to graphs with few edges in their neighbourhoods by Alon-Krivelevich and Sudakov, and to list chromatic number by Vu. I will give a full and self-contained proof of these results that relies only on induction and the first moment method.