Chordal Graphs, Even-Hole-Free Graphs and Sparse Obstructions to Bounded Treewidth

Even-hole-free graphs pose a central challenge in identifying hereditary classes of bounded treewidth. We investigate this matter by presenting and studying the following conjecture: for an integer (Formula presented.) and a graph (Formula presented.), every even-hole-free graph of large enough treewidth has an induced subgraph isomorphic to either (Formula presented.) or (Formula presented.), if (and only if) (Formula presented.) is a (Formula presented.) -free chordal graph. The “only if” part follows from the properties of the so-called layered wheels, a construction by Sintiari and Trotignon consisting of (even-hole, (Formula presented.))-free graphs with arbitrarily large treewidth. Alecu et al. proved recently that the conjecture holds in two special cases: (a) when (Formula presented.); and (b) when (Formula presented.) for some forest (Formula presented.); that is, (Formula presented.) is obtained from a forest (Formula presented.) by adding a universal vertex. Our first result is a common strengthening of (a) and (b): for an integer (Formula presented.) and graphs (Formula presented.) and (Formula presented.), (even-hole, (Formula presented.))-free graphs have bounded treewidth if and only if (Formula presented.) is a forest and (Formula presented.) is a (Formula presented.) -free chordal graph. Also, for general (Formula presented.), we push the current state of the art further than (b) by settling the conjecture for the smallest choices of (Formula presented.) that are not coned forests. The latter follows from our second result: we prove the conjecture when (Formula presented.) is a crystal; that is, a graph obtained from arbitrarily many coned double stars by gluing them together along the “middle” edges of the double stars. In the first version of this paper, we suggested the following which is a strengthening of our main conjecture: for every (Formula presented.), every graph of sufficiently large treewidth has an induced subgraph of treewidth (Formula presented.) which is either complete, complete bipartite, or 2-degenerate. This strengthening has now been refuted by Chudnovsky and Trotignon [On treewidth and maximum cliques, arxiv:2405.07471, 2024].