Courses
Background: Participants will be expected to know the material covered in Chapters 1-4
and section 5.1 of Doug West's text: Introduction to graph theory. The
courses will include some of the material in Chapters 6 and 7 and Sections
5.2 and 8.1. Lovasz's book Combinatorial Problems and Exercises
is a good source of harder warm-up problems.
You can access the following course materials with the user name and password we have sent you.
The courses offered are:
-
Structural results obtained from excluding graph minors
(lecturer: Bruce Reed):
The course will focus on the characterization of families of graphs obtained by forbidding a certain set of obstructions as minors. In particular, it surveys a seminal series of papers of Robertson and Seymour which presents a structural decomposition for H-minor free graphs, for any H, and uses this result to develop an algorithm for testing membership in any such minor-closed family. The 20th paper in this series was awarded the 2006
Fulkerson prize (jointly awarded by the AMS
and the Mathematical Programming
Society).
-
Structural results obtained by excluding induced subgraphs
(lecturers: Maria Chudnovsky and Paul Seymour):
The course will focus on the characterization of various families of graphs obtained by forbidding a certain set of obstructions as induced subgraphs. The results to be discussed include the proof of Berge's Strong Perfect Graph Conjecture (for which Chudnovsky, Robertson, Seymour, and Thomas were awarded the 2009 Fulkerson Prize), the structural characterization of claw-free graphs, and a proof of
some specific instances of the Erdos-Hajnal conjecture.
|