Induced subgraphs and tree decompositions

Treewidth is a graph parameter that roughly measures how "close to a tree'' G is. Graphs with small treewidth have nice structural and algorithmic properties: for example, many NP-hard algorithmic problems can be solved in polynomial time in graphs with constant or logarithmic treewidth. Graph classes defined by forbidden induced subgraphs are an active subject of interest and research in structural graph theory, but not much is currently understood regarding which hereditary graph classes have bounded treewidth. Recently, Korhonen provided a complete characterization of constant treewidth in the case of bounded maximum degree. In this talk, we discuss recent results showing that certain hereditary graph classes with unbounded degree have constant or logarithmic treewidth. The proofs use well-chosen collections of separations to iteratively decompose graphs into less complicated graphs while preserving the treewidth up to a constant factor. This talk is based on joint work with Maria Chudnovsky, Sepehr Hajebi, and Sophie Spirkl.