{"id":"arxiv/2611.14070","url":"https://arxiv.org/abs/2611.14070","tags":["math.CO"],"score":0,"title":"Treewidth versus Hadwiger number: Graph classes with dominated balanced separators are quasi-linearly treewidth-Hadwiger bounded","domain":"math.CO","source":"arxiv","authors":["Clément Dallard","J. Pascal Gollin","Andrea Munaro"],"reviews":0,"subject":"math.CO","summary":"In a hereditary graph class $\\mathcal{G}$, the treewidth of a graph in $\\mathcal{G}$ is bounded by a function of the size of a largest clique minor of the graph if and only if the class $\\mathcal{G}$ excludes some planar graph as an induced minor. Campbell et al. (arXiv 2024) conjectured that such a bounding function can always be chosen to be linear. We verify this conjecture for several classes of graphs (including even-hole-free graphs) and show that if a hereditary graph class $\\mathcal{G}$ has dominated binary-weighted balanced separators, then the bounding function can be taken to be…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}