Graphs and Matroids - Sepehr

Title: The pathwidth theorem for induced subgraphs

Abstract: 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. If time permits , we will also try to discuss the proof of the first result mentioned above.

Based on joint work with Maria Chudnovsky and Sophie Spirkl.