University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Colouring triangle-free graphs with few colours

## Colouring triangle-free graphs with few coloursAdd 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:Note that ex-directory lists are not shown. |
## Other listsBirmingham Popular Maths Lectures School of Mathematics Events Reading Group in Combinatorics and Probability## Other talksBest Response Dynamics on Random Graphs Generalised hydrodynamics and universalities of transport in integrable (and non-integrable) spin chains Quantum simulation of strongly correlated fermions: A theory perspective LovĂˇsz' Theorem and Comonads in Finite Model Theory |