Paul Seymour and Maria Chudnovsky

Lecture series on Structural Graph Theory

Mathematical Institute

University of Oxford


Monday 28 June-Friday 16 July, 2010


 Paul Seymour (Princeton) and Maria Chudnovsky (Columbia) will give a series of six lectures on Structural Graph Theory.  The first three lectures will on Mon/Wed/Fri in the week starting 28 June, and the second three on Mon/Wed/Fri in the week starting 12 July.  All lectures will be in at 11am, and will take place in L3 in the Mathematical Institute.  A brief description of the lecture series can be found below.



Structural Graph Theory

 Paul Seymour and Maria Chudnovsky


This is a series of talks on structural graph theory, six lectures over two weeks. The first week will cover perfect graphs (the proof of Berge's strong perfect graph conjecture, due to the speakers, Robertson and Thomas) and a polynomial-time algorithm to test if a graph is perfect. In the second week we will discuss some more recent results.

1 - Perfect graphs, background and basics
2 - Proof of the strong perfect graph theorem
3 - A polynomial time algorithm to test if a graph has an odd hole or antihole
4 - Structure of claw-free graphs
5 - Immersion in graphs and digraphs
6 - Rao's conjecture on degree sequences.