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 known bound for an arbitrary planar $H$ is $O(|V(H){|}^{9}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 being optimal.