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.
Alex Scott
Oxford University
Event Location: 
Fine Hall 224