event
ARC Colloquium: Mike Molloy (Univ. of Toronto)
Primary tabs
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}$.
--------------------------------------
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
Groups
Status
- Workflow Status:Published
- Created By:Francella Tonge
- Created:09/05/2017
- Modified By:Francella Tonge
- Modified:10/13/2017
Categories
Keywords
- No keywords were submitted.
Target Audience