Delphi.science

Treewidth versus Hadwiger number: Graph classes with dominated balanced separators are quasi-linearly treewidth-Hadwiger bounded

Source: arxiv.org/abs/2611.14070

Clément Dallard, J. Pascal Gollin, Andrea Munaro

arXivarxiv/2611.14070Nov 10, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.14070
curl -X POST /api/v1/records/arxiv/2611.14070/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.14070/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'