Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs

A classical result of Erdős and Pósa states that every graph that does not contain a union of constantly many cycles as a subgraph has bounded treewidth. The authors of the present paper study the induced version of the problem: what can be said about the treewidth of graphs that do not contain a union of $c$ cycles as an induced subgraph (or equivalently, that do not contain $c$ disjoint cycles with no edges between them)?

Note that complete graphs and complete bipartite graphs do not contain the union of 2 cycles as an induced subgraph, and they have arbitrarily large treewidth; so they need to be excluded as well. Several structure theorems on graphs of bounded treewidth also require the exclusion of grids or line-graphs of grids as an induced subgraph, but here this is not needed, as any sufficiently large grid or line-graph of a grid contains a union of many cycles as an induced subgraph.

It was proved in this paper that graphs on $n$ vertices that do not contain a union of $c$ cycles, nor the complete graph $K_c$ and the complete bipartite graph $K_{c,c}$ as induced subgraphs have treewidth logarithmic in $n$. Moreover this logarithmic bound is best possible, as shown by an explicit construction (let us call this a $c$-occultation). The main result of the present paper is that if in addition to a union of $c$ cycles, the complete graph $K_c$ and the complete bipartite graph $K_{c,c}$ we forbid a $c$-occultation (or more precisely a generalized version of the orginal construction) as an induced subgraph, then the graphs under consideration have constant treewidth. As all ingredients in the theorem are necessary, this gives the full list of obstructions to bounded treewidth in graphs that do not contain a union of $c$ cycles as an induced subgraph, and this is the first such result where the list contains some non basic obstructions (where the basic obstructions are complete and complete bipartite graphs, grids and their line-graphs). The result extends to graphs that do not contain the union of $c$ cycles of length at least $k$ as an induced subgraph. In a subsequent paper, a subset of the authors has extended the result to graphs that do not contain the union of $c$ graphs of treewidth at least $k$ as an induced subgraph.