Bounds on Treewidth via Excluding Disjoint Unions of Cycles

Abstract

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.