Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · Innovations in Graph Theory · 2025
Given c ∈ ℕ , we say a graph G is c -pinched if G does not contain an induced subgraph consisting of c cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of c -pinched graphs? For instance, 1 -pinched graphs are exactly graphs of treewidth 1 . However, bounded treewidth for c > 1 is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of 2 -pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of c , discovered by Pohoata and later independently by Davies, consisting of 3 -pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions. We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every c ∈ ℕ , a c -pinched graph G has large treewidth if and only if G contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line graph of a subdivision of a large wall, or a large graph from the Pohoata–Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded.