Computer Science/Discrete Mathematics Seminar I

Tree decompositions, and in particular path decompositions, are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph.

Families of bounded treewith and pathwidth have been completely characterized in terms of forbidden subgraphs (and minors) in the 1990s.  Studying this question in connection with graph containment relations of more local flavor (such as induced subgraph or induced minors) is a relatively new research direction. In this talk we will present a recent result that provides a complete list of induced subgraph obstructions to bounded pathwidth.

This is joint work with Sepehr Hajebi and Sophie Spirkl, building on earlier results of the series "Induced subgraphs and tree decompositions", that is currently comprised of 18 papers.