Bounds on Treewidth via Excluding Disjoint Unions of Cycles
One of the fundamental results in graph minor theory is that for every planar graph $H$, there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to~$H$ have treewidth at most $f(H)$. The best bound known for an arbitrary planar $H$ is ${O(|V(H)|^9\operatorname{poly~log}|V(H)|)}$. We show that if $H$ is the disjoint union of cycles, then $f(H)$ is $O(|V(H)|\log^2 |V(H)|)$, which is a $\log|V(H)|$ factor away from being optimal.
Authors
- Meike Hatzel (ORCID: https://orcid.org/0000-0003-3249-1169)
- Sebastian Wiederrecht (ORCID: https://orcid.org/0000-0003-0462-7815)
- Chun‐Hung Liu (ORCID: https://orcid.org/0000-0001-8822-9966)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2026-10-09
- DOI
- https://doi.org/10.37236/13735
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Deutscher Akademischer Austauschdienst
- Bundesministerium für Bildung und Forschung
- Institute for Basic Science