{"ID":2869595,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.15458","arxiv_id":"2509.15458","title":"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 $ω(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 $ω(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)|)$.","short_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...","url_abs":"https://arxiv.org/abs/2509.15458","url_pdf":"https://arxiv.org/pdf/2509.15458v1","authors":"[\"Maria Chudnovsky\",\"Julien Codsi\"]","published":"2025-09-18T22:05:43Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}