Structure Theorems in Graph Theory
Topic
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.
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.
Speakers
Additional Information
10th Anniversary Speaker Series 2007
Paul Seymour (Princeton University)c
Paul Seymour (Princeton University)c