k-Blocks and forbidden induced subgraphs

Thursday, September 21, 2023 - 4:00pm for 1 hour (actually 50 minutes)
Skiles 005
Maria Chudnovsky – Princeton University – https://web.math.princeton.edu/~mchudnov/
Anton Bernshteyn

Atlanta Combinatorics Colloquium Hosted by Georgia Tech

A k-block in a graph is a set of k vertices every two of which are joined by k vertex disjoint paths. By a result of Weissauer, graphs with no k-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions to bounded tree width, a lot can be said about graphs with no k-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a k-block in a graph. We will discuss this phenomenon and its consequences on the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.