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

 

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

Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu

Event Details

Date/Time:

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