The chromatic number of graphs without long holes

Thursday, September 24, 2015 -
3:00pm to 4:00pm
Andras Gyarfas conjectured in 1985 that for all k and t, every graph with sufficiently large chromatic number contains either a complete subgraph on k vertices or an induced cycle of length at least t. We prove this conjecture and discuss some related results. Joint work with Maria Chudnovsky and Paul Seymour.
Speaker: 
Alex Scott
Oxford University
Event Location: 
Fine Hall 224