Title: Bounded treewidth in hereditary graph classes
| Speaker: | Sepehr Hajebi |
| Affiliation: | University of Waterloo |
| Location: | MC 5417 |
Abstract: A highlight of the superb graph minors project of Robertson and Seymour is their so-called Grid Theorem: a minor-closed class of graphs has bounded treewidth if and only it does not contain all planar graphs. Which induced-subgraph-closed graph classes have bounded treewidth? There is not even a rigorous conjecture proposing a general answer to this question. Nevertheless, several results toward a ``grid theorem for induced subgraphs’’ have been discovered over the course of the past few years. I will give an overview of the current state of the art in this area.
Based
on
joint
work
with
Tara
Abrishami,
Bogdan
Alecu,
Maria
Chudnovsky,
Cemil
Dibek,
Pawel
Rzazewski,
Sophie
Spirkl,
and
Kristina
Vuskovic.