Bounds on treewidth via excluding disjoint unions of cycles
arXiv:2501.017038.72 citationsh-index: 7
Predicted impact top 60% in CO · last 90 daysOriginality Incremental advance
AI Analysis
For graph theorists, this tightens a key bound in graph minor theory for a specific class of planar graphs.
The paper improves the upper bound on treewidth for graphs excluding a disjoint union of cycles as a minor, achieving O(|V(H)| log² |V(H)|), which is within a log factor of optimal.
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\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 being optimal.