On February 25, 2025, Sepehr Hajebi from the University of Waterloo gave a talk at the Discrete Math Seminar on unavoidable induced subgraphs of graphs of large path-width. The title of his talk was “The pathwidth theorem for induced subgraphs“.
Sepehr Hajebi, The pathwidth theorem for induced subgraphs
We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor.
We will also try to discuss the proof of the first result with as much detail as time permits.
Based on joint work with Maria Chudnovsky and Sophie Spirkl.
Sepehr Hajebi gave an online talk on bounding the tree-width of graphs with forbidden induced subgraphs at the Virtual Discrete Math Colloquium
On July 7, 2022, Sepehr Hajebi from the University of Waterloo gave an online talk at the Virtual Discrete Math Colloquium on bounding the tree-width of graphs with forbidden induced subgraphs. The title of his talk was “Holes, hubs and bounded treewidth“.