SPECIAL
YEAR ON GRAPH THEORY AND COMBINATORIAL OPTIMIZATION
## Coxeter Lecture Series

### Presentation on Graph Minors -- Special Guest Lecturer

Paul Seymour of the Mathematical Institute, Princeton University

### January 17 to 19, 2000

An overview of the theory of graph minors, and results based on the research
of Neil Robertson and Paul Seymour.

**Some of the topics to be covered are:**

An Introduction to Graph Minors

Graph Minors: Sketches of Some Proofs

Graph Minors: Current Research

*For any fixed planar graph H, all graphs not containing H as a minor are
expressible as tree-structures of bounded size pieces (this is false for every
non-planar H).

*For any fixed graph H, all graphs not containing H as a minor are expressible
as tree-structures of pieces that are "almost" of bounded genus.

*Wagner's conjecture (now a theorem): for any infinite set of graphs, one
of them is a minor of another. Consequently, any property of graphs that can
be characterized by excluded minors can also be characterized by excluding
just finitely many minors.

*A polynomial time algorithm for the k paths problem, for fixed k - we are
given k pairs of vertices of a graph, and want to test whether there are k
vertex-disjoint paths linking the pairs.

###