{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T02:28:28Z","timestamp":1787365708376,"version":"build-2736575974"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2013,7,8]],"date-time":"2013-07-08T00:00:00Z","timestamp":1373241600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph <jats:italic>H<\/jats:italic> as a minor has the so-called Erd\u0151s\u2013P\u00f3sa property; namely, there exists a function <jats:italic>f<\/jats:italic> depending only on <jats:italic>H<\/jats:italic> such that, for every graph <jats:italic>G<\/jats:italic> and every positive integer <jats:italic>k<\/jats:italic>, the graph <jats:italic>G<\/jats:italic> has <jats:italic>k<\/jats:italic> vertex-disjoint subgraphs each containing <jats:italic>H<\/jats:italic> as a minor, or there exists a subset <jats:italic>X<\/jats:italic> of vertices of <jats:italic>G<\/jats:italic> with |<jats:italic>X<\/jats:italic>| \u2264 <jats:italic>f(k)<\/jats:italic> such that <jats:italic>G \u2212 X<\/jats:italic> has no <jats:italic>H<\/jats:italic>-minor (see Robertson and Seymour, <jats:italic>J. Combin. Theory Ser. B<\/jats:italic><jats:bold>41<\/jats:bold> (1986) 92\u2013114). While the best function <jats:italic>f<\/jats:italic> currently known is exponential in <jats:italic>k<\/jats:italic>, a <jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic> log <jats:italic>k<\/jats:italic>) bound is known in the special case where <jats:italic>H<\/jats:italic> is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function <jats:italic>f<\/jats:italic> can be taken to be linear when <jats:italic>H<\/jats:italic> is a forest. This is best possible in the sense that no linear bound is possible if <jats:italic>H<\/jats:italic> has a cycle.<\/jats:p>","DOI":"10.1017\/s0963548313000266","type":"journal-article","created":{"date-parts":[[2013,7,8]],"date-time":"2013-07-08T07:43:28Z","timestamp":1373269408000},"page":"700-721","source":"Crossref","is-referenced-by-count":9,"title":["Excluded Forest Minors and the Erd\u0151s\u2013P\u00f3sa Property"],"prefix":"10.1017","volume":"22","author":[{"given":"SAMUEL","family":"FIORINI","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"GWENA\u00cbL","family":"JORET","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"DAVID R.","family":"WOOD","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2013,7,8]]},"reference":[{"key":"S0963548313000266_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"S0963548313000266_ref21","doi-asserted-by":"crossref","unstructured":"Kim E. J. , Paul C. and Philip G. A single-exponential FPT algorithm for the K 4-minor cover problem. In Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory: SWAT 2012, to appear. arXiv:1204.1417","DOI":"10.1007\/978-3-642-31155-0_11"},{"key":"S0963548313000266_ref22","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1788"},{"key":"S0963548313000266_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20503"},{"key":"S0963548313000266_ref1","first-page":"641","volume-title":"Proc. Nineteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"Adler","year":"2008"},{"key":"S0963548313000266_ref14","first-page":"189","volume-title":"Proc. 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)","author":"Fomin","year":"2011"},{"key":"S0963548313000266_ref23","unstructured":"Leaf A. and Seymour P. Treewidth and planar minors. Preprint. http:\/\/web.math.princeton.edu\/~pds\/papers\/treewidth\/paper.pdf"},{"key":"S0963548313000266_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001450"},{"key":"S0963548313000266_ref13","unstructured":"Fomin F. V. , Lokshtanov D. , Misra N. and Saurabh S. (2012) Foundations of Computer Science (FOCS). In Proc. IEEE 53rd Annual Symposium on, Planar F-Deletion: Approximation, Kernelization and Optimal FPTAlgorithms, pp. 470\u2013479."},{"key":"S0963548313000266_ref4","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Vol. B","author":"Courcelle","year":"1990"},{"key":"S0963548313000266_ref28","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"S0963548313000266_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"S0963548313000266_ref5","first-page":"159","volume-title":"Proc. 6th International Symposium on Parameterized and Exact Computation, Saarbr\u00fccken, Germany","author":"Cygan","year":"2011"},{"key":"S0963548313000266_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.08.001"},{"key":"S0963548313000266_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90068-U"},{"key":"S0963548313000266_ref10","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1064"},{"key":"S0963548313000266_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_34"},{"key":"S0963548313000266_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"S0963548313000266_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17493-3_11"},{"key":"S0963548313000266_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16926-7_19"},{"key":"S0963548313000266_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"S0963548313000266_ref16","first-page":"357","volume-title":"Logic and Automata: History and Perspectives","author":"Grohe","year":"2008"},{"key":"S0963548313000266_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6"},{"key":"S0963548313000266_ref20","first-page":"278","volume-title":"Proc. 29th International Symposium on Theoretical Aspects of Computer Science: STACS 2012","author":"Kawarabayashi","year":"2012"},{"key":"S0963548313000266_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993700"},{"key":"S0963548313000266_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_15"},{"key":"S0963548313000266_ref3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"S0963548313000266_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"S0963548313000266_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"},{"key":"S0963548313000266_ref11","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T20:04:13Z","timestamp":1556049853000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000266\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,8]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["S0963548313000266"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000266","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,8]]}}}