## ARC Colloquium: Mike Molloy (Univ. of Toronto)

Algorithms & Randomness Center (ARC)

Mike Molloy (Univ. of Toronto)

Friday, October 20, 2017

Skiles 005 - 11:00 am

Abstract:

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\geq4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{\D\ln\ln\D}{\ln\D}$.

--------------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836