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

Colouring triangle-free graphs with few colours

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

  • UserAnton Bernshteyn (University of Illinois at Urbana-Champaign)
  • ClockWednesday 30 May 2018, 15:00-16:00
  • HouseWatson 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.