Graph and Matroids Seminar - Sepehr Hajebi

Tuesday, July 5, 2022 2:30 pm - 2:30 pm EDT (GMT -04:00)

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.