Linear bounds on treewidth in terms of excluded planar minors

Jochen Pascal Gollin¹ ; Kevin Hendrey² ; Sang-il Oum³ ; Bruce Reed⁴

¹Institute for Basic Science
²Insitute for Basic Science
³Insitute for Basic Science and KAIST
⁴Academia Sinica

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

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)$. A lower bound for ${f(H)}$ can be obtained by considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth ${\Omega(k\log k)}$ which does not contain $k$ vertex-disjoint cycles, from which it follows that ${f(H) = \Omega(k\log k)}$. In particular, if ${f(H)}$ is linear in $|V(H)|$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$-vertex graphs from the class contain at most ${O(n/\log n)}$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$-vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$, and improve this to ${f(H) \leq n + O(\sqrt{n})}$ when ${r = 2}$. In particular this bound is linear when ${r=O(\sqrt{n}/\log n)}$. We present a linear bound for ${f(H)}$ when $H$ is a subdivision of an $r$-edge planar graph for any constant~$r$. We also improve the best known bounds for ${f(H)}$ when $H$ is the wheel graph or the ${4 \times 4}$ grid, obtaining a bound of $160$ for the latter.

Détail

DOI : 10.37236/12834

Classification : 05C83