{"id":"arxiv/2609.24684","url":"https://arxiv.org/abs/2609.24684","tags":["math.CO","cs.DS"],"score":0,"title":"Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number","domain":"math.CO","source":"arxiv","authors":["Andrea Munaro"],"reviews":0,"subject":"math.CO","summary":"We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth. In fact, this is part of a broader equivalence theorem. For hereditary classes, these conditions are also equivalent to having clique-dependent polynomial expansion, to admitting balanced separators whose size is bounded by…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-21","reactions":{}}