Tree-independence number VI. Thetas and pyramids

Abstract

Given a family $\mathcal{H}$ of graphs, we say that a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. Let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid and let ${\mathcal{L}}_t$ be the family of all graphs $G$ such that $G$ is the line graph of some subdivision of $W_{t\times t}$. We denote by $\ddot{I}‰(G)$ the size of the largest clique in $G$. We prove that for every integer $t$ there exist integers $c_1(t)$, $c_2(t)$ and $d(t)$ such that every (pyramid, theta, ${\mathcal{L}}_t$)-free graph $G$ satisfies: i) $G$ has a tree decomposition where every bag has size at most $\ddot{I}‰(G{)}^{c_1(t)}\log (|V(G)|)$. ii) If $G$ has at least two vertices, then $G$ has a tree decomposition where every bag has independence number at most ${\log }^{c_2(t)}(|V(G)|)$. iii) For any weight function, $G$ has a balanced separator that is contained in the union of the neighborhoods of at most $d(t)$ vertices. These results qualitatively generalize the main theorems of Abrishami et al. (2022) and Chudnovsky et al. (2024). Additionally, we show that there exist integers $c_3(t),c_4(t)$ such that for every (theta, pyramid)-free graph $G$ and for every non-adjacent pair of vertices $a,b\in V(G)$, i) $a$ can be separated from $b$ by removing at most $w(G{)}^{c_3(t)}\log (|V(G)|)$ vertices. ii) $a$ can be separated from $b$ by removing a set of vertices with independence number at most ${\log }^{c_4(t)}(|V(G)|)$.

27 pages, 6 figures