***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 15th September, 3:00 in Fine Hall 224.
 
Speaker: Alex Scott (Oxford)

Title: Maximising the number of induced cycles

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.


                       -----------

Next week: Gil Cohen

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)