Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth

A classical result of Roberston and Seymour is that every graph of sufficiently large treewidth contains a large grid as a minor. As grids themselves have large treewidth, they form a natural certificate for having large treewidth. Robertson and Seymour also showed that similarly, every graph of sufficiently large pathwidth contains a large binary tree as a minor (and large binary trees themselves have large pathwidth). A natural question is whether similar certificates exist not for the relation of minors or subgraphs, but instead for induced subgraphs.

A recent result shows that no such (non-trivial) certificate exist for treewidth. In the present paper it is shown that, on the other hand, such certificates exist for pathwidth. More precisely, it is proved that a graph of large pathwidth must contain as an induced subgraph one of the following: a large complete or complete bipartite graph, a large subdivided binary tree or its line graph, or a large “constellation”, which is a union of disjoint paths together with a large independent set of vertices whose neighbors in the paths are appropriately intertwined.

This characterization follows from a characterization similar to that of Robertson and Seymour for induced minors rather than minors, including large complete graphs and complete bipartite graphs in addition to large binary trees.