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.