Tue, 15 Mar 2022
14:00
14:00
C6
Colouring locally sparse graphs with the first moment method
Eoin Hurley
(Heidelberg University)
Abstract
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.