The list chromatic number of graphs with small clique number (joint with ARC; note the unusual time!)

Combinatorics Seminar
Friday, October 20, 2017 - 13:00
1 hour (actually 50 minutes)
Skiles 005
University of Toronto
We prove that every triangle-free graph with maximum degree $D$ has list chromatic number at most $(1+o(1))\frac{D}{\ln D}$. This matches the best-known bound for graphs of girth at least 5.  We also provide a new proof  that for any $r \geq 4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{D\ln\ln D}{\ln D}$.