Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth

Abstract

We present and study the following conjecture: for an integer $t\ge 4$ and a graph $H$, every even-hole-free graph of large enough treewidth has an induced subgraph isomorphic to either $K_t$ or $H$, if (and only if) $H$ is a $K_4$-free chordal graph. The ``only if'' part follows from the properties of the so-called layered wheels due to Sintiari and Trotignon. Alecu, Chudnovsky, Spirkl and the author recently proved the conjecture in two special cases: (a) when $t=4$; and (b) when $H=cone(F)$ for some forest $F$; that is, $H$ is obtained from $F$ by adding a universal vertex. Our first result is a common strengthening: for an integer $t\ge 4$ and graphs $F$ and $H$, (even-hole, $cone(cone(F))$, $H$, $K_t$)-free graphs have bounded treewidth if and only if $F$ is a forest and $H$ is a $K_4$-free chordal graph. Also, for general $t\ge 4$, we push the current state of the art further than (b) by settling the conjecture for the smallest choices of $H$ that are not coned forests. This follows from our second result: we prove the conjecture when $H$ is a crystal; that is, a graph obtained from several coned double stars by gluing them together along the middle edges of the double stars. In the first version of this paper, we suggested a strengthening of our main conjecture, that for every $t\ge 1$, every graph of sufficiently large treewidth has an induced subgraph of treewidth $t$ 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].

References in corpus (5)

• Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$-free graphs
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Induced subgraphs and tree decompositions VIII. Excluding a forest in (theta, prism)-free graphs
• Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$
• Induced subdivisions with pinned branch vertices

Cited by in corpus (1)

• On treewidth and maximum cliques