Induced subgraphs and tree decompositions XIII. Basic obstructions in H-free graphs for finite H

Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every t ∈ N, the t-basic obstructions: the graphs K_t+1 and K_t,t, along with the subdivisions of the t-by-t wall and their line graphs. But this list is far from complete. The simplest example of a “non-basic” obstruction is due to Pohoata and Davies (independently). For every n ∈ N, they construct certain graphs of treewidth n and with no 3-basic obstruction as an induced subgraph, which we call n-arrays. Let us say a graph class G is clean if the only obstructions to bounded treewidth in G are in fact the basic ones. It follows that a full description of the induced subgraph obstructions to bounded treewidth is equivalent to a characterization of all families H of graphs for which the class of all H-free graphs is clean (a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H). This remains elusive, but there is an immediate necessary condition: if H-free graphs are clean, then there are only finitely many n ∈ N such that there is an n-array which is H-free. The above necessary condition is not sufficient in general. However, the situation turns out to be different if H is finite: we prove that for every finite set H of graphs, the class of all H-free graphs is clean if and only if there is no H-free n-array except possibly for finitely many values of n.