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 listsType the title of a new list here Type the title of a new list here Type the title of a new list here## Other talksThe Griess Algebra and the Monster Plundervolt: Pillaging and plundering SGX with Software-based Fault Injection Attacks Gravitational wave progenitors near and far Weak universalities for some singular stochastic PDEs A quotient geometry on the manifold of fixed-rank positive-semidefinite matrices Privileged side-channel attacks for enclave adversaries |