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