- Thursday, September 21, 2023 - 16:00 for 1 hour (actually 50 minutes)
- Skiles 005
- Maria Chudnovsky – Princeton University
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.