Upper Bounds on the Chromatic Number for Triangle-Free Graphs

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\'asz 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\'asz Local Lemma developed by Moser and Tardos. In this talk, I will present 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 nonstandard way). I will also talk about some extensions of this result to more general notions of coloring, such as list and DP-coloring.

Event Topic

Discrete Applied Math Seminar