{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T16:12:48Z","timestamp":1765469568153,"version":"3.48.0"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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.\u00a0<\/jats:p>","DOI":"10.37236\/12834","type":"journal-article","created":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T16:08:10Z","timestamp":1765469290000},"source":"Crossref","is-referenced-by-count":0,"title":["Linear Bounds on Treewidth in Terms of Excluded Planar Minors"],"prefix":"10.37236","volume":"32","author":[{"given":"Jochen Pascal","family":"Gollin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Hendrey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sang-il","family":"Oum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce","family":"Reed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2025,12,12]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v32i4p68\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v32i4p68\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T16:08:10Z","timestamp":1765469290000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v32i4p68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,12]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,10,3]]}},"URL":"https:\/\/doi.org\/10.37236\/12834","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,12]]},"article-number":"P4.68"}}