Characterizing families of hereditary graph classes

Christopher Purcell

Aalto University - Finland

Friday, November 17th, 4:30PM

Kalkin – Room 001

Abstract:

The famous theorem of Robertson and Seymour states that graphs are well-quasi-ordered by the minor

relation. This tells us that every minor-closed graph class can be characterized by a finite list

of minimal forbidden minors. As a result, every set of minor-closed graph classes has a minimal

element under the containment relation. Thus, we may characterize a family of minor- closed classes

by listing the minimal classes outside the family. Characterizing families of classes closed under

vertex deletion (hereditary classes) is more challenging. Since graphs are not well-quasi-ordered

by the induced subgraph relation, there need not be a minimal element of a set of hereditary

classes in general. To overcome this difficulty, new machinery was developed which will be

described in this talk. We will give an overview of the main results and techniques, and of the

applications to computational complexity and other areas. This talk will be accessible to graduate

students in mathematics and computer science.

ADA: Individuals requiring accommodations, please contact Doreen Taylor at (802) 656-3166

REFRESHMENTS WILL BE SERVED.