Maximising the number of induced cycles

Thursday, September 15, 2016 -
3:00pm to 4:30pm
How many holes can a graph on n vertices contain?  How many induced cycles? For sufficiently large n, we determine the maximum number of induced cycles, the maximum number of holes, and the maximum number of even or odd induced cycles, and in each case characterize the graphs achieving this bound. This answers a question of Tuza, and a conjecture of Chvatal and Tuza from 1988.  Joint work with Natasha Morrison. 
Alex Scott
Oxford University
Event Location: 
Fine Hall 224