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.
