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

A classical theorem of Robertson and Seymour states that every graph of large treewidth contains a large grid as a minor, or equivalently a subdivision of a large hexagonal grid (also called a wall) as a subgraph. This theorem has been crucial both from the structural and algorithmic point of view, as a large number of combinatorial problems can be solved efficiently on graphs of bounded treewidth. So a classical algorithmic approach is to do the following: either our graph $G$ has bounded treewidth and we can solve the problem efficiently, or $G$ contains a subdivision of a large wall and then the goal is to show that some vertex $v$ in the middle of the wall is irrelevant for the problem (the problem has the same solution in $G$ and in $G-v$). This is typically the case in disjoint paths problems, where the wall can be used to reroute any path that would contain $v$.

Minor and subgraph obstructions to large treewidth are thus well-understood, but it is not the case of induced subgraph obstructions. This would in particular be useful in the (structural or algorithmic) study of hereditary classes.

In addition to walls, a number of additional natural induced obstructions appear: for instance cliques and complete bipartite graphs. We also have to forbid line-graphs of walls. Let us call these four obstructions “basic”. Is it the complete list of induced obstructions to large treewidth ?

Unfortunately a number of quite different constructions show that the list above is not complete. In particular, there is a nice construction by Pohoata and Davies (independently), called “array”, which is as follows. Take $n$ disjoints paths $P_1,\ldots,P_n$ and add $n$ vertices $x_1,\ldots,x_n$ such that each vertex $x_i$ is adjacent to all paths, and on each path $P_j$, the neighbors of $x_1, \ldots,x_n$ are ordered, that is for any $x_i$ and $x_k$ with $i<k$ the neighbors of $x_i$ appear before the neighbors of $x_k$ on $P_j$. This is called an $n$-array, and it can be checked that it does not contain any large basic obstructions , while it has treewidth at least $n$.

So if we want to characterize graphs classes in which the only induced obstructions to large treewidth are the basic ones, we certainly need to forbid arbitrarily large arrays. The main result of the paper is that if a graph class has a finite number of forbidden induced subgraphs, and in addition does not contain arbitrarily large arrays, then the only induced obstructions to large treewidth are the basic ones (large cliques, complete bipartite graphs, walls and their line-graphs).

The obstructions considered in the paper have a nice interpretation in terms of combinatorics on words and the paper concludes with a number of stimulating questions in this area.