Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graphs of large treewidth

Abstract

We prove a conjecture of Sintiari and Trotignon that every even-hole-free graph of sufficiently large treewidth contains a four-vertex induced subgraph with at least five edges (that is, either the four-vertex complete graph or the unique four-vertex graph with five edges, also known as the diamond). In fact, we prove two stronger results: (a) For every $K_4$-free chordal graph $H$, every even-hole-free graph of sufficiently large treewidth contains either a four-vertex complete subgraph or an induced subgraph isomorphic to $H$ (when $H$ is the diamond, this yields their conjecture); and (b) For every $K_3$-free chordal graph $H$ (equivalently, for every forest $H$) and every $t\in \mathbb{N}$, every even-hole-free graph of sufficiently large treewidth contains either a $t$-vertex complete subgraph or an induced subgraph obtained from $H$ by adding a universal vertex (when $t=4$ and $H$ is the three-vertex path, this yields their conjecture). The choice of $H$ in both result is best possible: (a) fails for every graph $H$ that is not $K_4$-free and chordal, and (b) fails for every graph $H$ that is not a forest.