(Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 2 : bounds on treewidth

Abstract

A {\em theta} is a graph made of three internally vertex-disjoint chordless paths $P_1=a\dots b$, $P_2=a\dots b$, $P_3=a\dots b$ of length at least~2 and such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A {\em pyramid} is a graph made of three chordless paths $P_1=a\dots b_1$, $P_2=a\dots b_2$, $P_3=a\dots b_3$ of length at least~1, two of which have length at least 2, vertex-disjoint except at $a$, and such that $b_1{b}_2{b}_3$ is a triangle and no edges exist between the paths except those of the triangle and the three edges incident to~$a$. An \emph{even hole} is a chordless cycle of even length. For three non-negative integers $i\le j\le k$, let $S_{i,j,k}$ be the tree with a vertex $v$, from which start three paths with $i$, $j$, and $k$ edges respectively. We denote by $K_t$ the complete graph on $t$ vertices. We prove that for all non-negative integers $i,j,k$, the class of graphs that contain no theta, no $K_3$, and no $S_{i,j,k}$ as induced subgraphs have bounded treewidth. We prove that for all non-negative integers $i,j,k,t$, the class of graphs that contain no even hole, no pyramid, no $K_t$, and no $S_{i,j,k}$ as induced subgraphs have bounded treewidth. To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality.