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.