Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Published 2022-12-06Version 1

Let us call a class $\mathcal{C}$ of graphs clean if for every positive integer $t$ there exists $w(t)$ such that every graph in $\mathcal{C}$ with treewidth more than $w(t)$ contains an induced subgraph isomorphic to one of the following: the complete graph $K_t$, the complete bipartite graph $K_{t,t}$, a subdivision of the $(t\times t)$-wall or the line graph of a subdivision of the $(t \times t)$-wall. In this paper, we use a method due to Lozin and Razgon (building on earlier ideas of Wei{\ss}auer) in order to characterize the graphs $H$ for which the class of $H$-free graphs is clean. Specifically, this is the case if and only if $H$ is a forest whose components are subdivided stars. Their method (which was used to characterize graphs $H$ whose absence implies bounded treewidth) is readily adapted to yield the above characterization. However, our main result is in fact stronger: we show that forbidding certain connected graphs containing $H$ (rather than $H$ itself) is enough to guarantee cleanness. To obtain this strengthening, we build on a result of Davies and produce a complete description -- of independent interest -- of unavoidable connected induced subgraphs containing $\eta \in \mathbb N$ vertices from a suitably large given set.