# Colouring triangle-free graphs with few colours

• Anton Bernshteyn (University of Illinois at Urbana-Champaign)
• Wednesday 30 May 2018, 15:00-16:00
• Watson LTA.

A classical theorem of Johansson from 1996 asserts that $\chi(G) = O(\Delta/\ln\Delta)$ for triangle-free graphs $G$ of maximum degree $\Delta$. Johansson’s original proof of this result was quite intricate and involved iterated applications of the Lov\’{a}sz Local Lemma. Recently, Molloy has sharpened Johansson’s bound to $\chi(G) \leq (1+o(1))\Delta/\ln\Delta$ using the so-called entropy compression method—-an algorithmic alternative to the Lov\’{a}sz Local Lemma developed by Moser and Tardos. In this talk, I will sketch a simple proof of the Johansson—Molloy theorem that avoids the technicalities of the entropy compression method and only uses the standard Local Lemma (albeit in a somewhat unusual way). I will also mention some extensions of this result to more general notions of colouring, such as list and correspondence colouring.

This talk is part of the Combinatorics and Probability Seminar series.