## Structure Theorems in Graph Theory

- Date: 08/31/2007

Paul Seymour (Princeton University)c

Simon Fraser University

Fix a graph H. What is the most general graph that does not contain H?

In other words, how do we explicitly construct all the graphs that do

not contain H?

To begin to make this precise, we have to say what 'contain' means;; we

have in mind either minor containment, or induced subgraph containment.

But what do we mean by an 'explicit construction' of a class of graphs?

We give some examples, and describe some connections and differences

between the two containment relations, and discuss several open

questions in the area. There will be no detailed proofs, and very

little knowledge of graph theory will be assumed.

10th Anniversary Speaker Series 2007