Colouring triangle-free graphs with few colours

Add to your list(s) Download to your calendar using vCal

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

If you have a question about this talk, please contact Allan Lo.

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.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTA

Note that ex-directory lists are not shown.