{"id":"arxiv/2605.01223","url":"https://arxiv.org/abs/2605.01223","tags":["math.CO"],"score":0,"title":"Tree-alpha and excluding finitely many graphs","domain":"math.CO","source":"arxiv","authors":["Sepehr Hajebi","Sophie Spirkl"],"reviews":0,"subject":"math.CO","summary":"We prove that a hereditary graph class $\\mathcal{G}$ defined by finitely many excluded induced subgraphs has bounded tree-$α$ if and only if it is \"$(\\mathrm{tw},ω)$-bounded\" (that is, for all $t\\in \\mathbb N$, the class of all $K_t$-free graphs in $\\mathcal{G}$ has bounded treewidth). Equivalently, $\\mathcal{G}$ has bounded tree-$α$ if and only if it excludes a complete bipartite graph, a forest whose components each have at most three leaves, and the line graph of such a forest. This resolves two conjectures of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht: the above, and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-02","reactions":{}}