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.

Other Information: 

10th Anniversary Speaker Series 2007