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


Title:  The list chromatic number of graphs with small clique number



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:

Click here to subscribe to the seminar email list:

Event Details


  • Friday, October 20, 2017
    11:00 am - 12:00 pm
Location: Skiles 005