{"id":"arxiv/2607.12090","url":"https://arxiv.org/abs/2607.12090","tags":["math.CO","cs.DM","cs.DS"],"score":0,"title":"Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence","domain":"math.CO","source":"arxiv","authors":["Maria Chudnovsky","Julien Codsi","Ajaykrishnan E S","Daniel Lokshtanov"],"reviews":0,"subject":"math.CO","summary":"An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ: V(T) \\rightarrow 2^{V(G)}$ is a function satisfying two axioms: for every edge $uv \\in E(G)$ there is an $x \\in V(T)$ such that $\\{u,v\\} \\subseteq χ(x)$, and for every vertex $u \\in V(G)$ the set $\\{x \\in V(T) | u \\in χ(x)\\}$ induces a non-empty and connected subtree of $T$. The sets $χ(x)$ for $x \\in V(T)$ are called the bags of the tree decomposition. The tree-independence number of $G$ is the minimum taken over all tree decompositions of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}