{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T21:18:11Z","timestamp":1718745491874},"reference-count":18,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2013,1,24]],"date-time":"2013-01-24T00:00:00Z","timestamp":1358985600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2013,12]]},"abstract":"Abstract<\/jats:title>According to the classical Erd\u0151s\u2013P\u00f3sa theorem, given a positive integer k<\/jats:italic>, every graph G<\/jats:italic> either contains k<\/jats:italic> vertex disjoint cycles or a set of at most vertices that hits all its cycles. Robertson and Seymour (J Comb Theory Ser B 41 (1986), 92\u2013114) generalized this result in the best possible way. More specifically, they showed that if is the class of all graphs that can be contracted to a fixed planar graph H<\/jats:italic>, then every graph G<\/jats:italic> either contains a set of k<\/jats:italic> vertex\u2010disjoint subgraphs of G<\/jats:italic>, such that each of these subgraphs is isomorphic to some graph in or there exists a set S<\/jats:italic> of at most vertices such that contains no subgraph isomorphic to any graph in . However, the function f<\/jats:italic> is exponential. In this note, we prove that this function becomes quadratic when consists all graphs that can be contracted to a fixed planar graph . For a fixed c<\/jats:italic>, is the graph with two vertices and parallel edges. Observe that for this corresponds to the classical Erd\u0151s\u2013P\u00f3sa theorem.<\/jats:p>","DOI":"10.1002\/jgt.21720","type":"journal-article","created":{"date-parts":[[2013,1,25]],"date-time":"2013-01-25T02:00:59Z","timestamp":1359079259000},"page":"417-424","source":"Crossref","is-referenced-by-count":6,"title":["Quadratic Upper Bounds on the Erd\u0151s\u2013P\u00f3sa Property for a Generalization of Packing and Covering Cycles"],"prefix":"10.1002","volume":"74","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"DEPARTMENT OF INFORMATICS UNIVERSITY OF BERGEN N\u20105020 BERGEN NORWAY"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"UNIVERSITY OF CALIFORNIA SAN DIEGO LA JOLLA CA 92093\u20100404"}]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[{"name":"THE INSTITUTE OF MATHEMATICAL SCIENCES CHENNAI 600113 INDIA"}]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[{"name":"THE INSTITUTE OF MATHEMATICAL SCIENCES CHENNAI 600113 INDIA"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"THE INSTITUTE OF MATHEMATICAL SCIENCES CHENNAI 600113 INDIA"}]}],"member":"311","published-online":{"date-parts":[[2013,1,24]]},"reference":[{"key":"e_1_2_4_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018373005182"},{"key":"e_1_2_4_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0047-0"},{"key":"e_1_2_4_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7643-7400-6_4"},{"key":"e_1_2_4_5_1","first-page":"195","article-title":"Unboundedness for generalized odd cyclic transversality","volume":"52","author":"Dejter I. J.","year":"1988","journal-title":"Colloq. Math. Soc. J\u00e1nos Bolyai. North\u2010Holland, Amsterdam"},{"key":"e_1_2_4_6_1","volume-title":"Graph Theory, volume 173 of Graduate Texts in Mathematics","author":"Diestel R.","year":"2005"},{"key":"e_1_2_4_7_1","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u00f6s P.","year":"1935","journal-title":"Compositio Math"},{"key":"e_1_2_4_8_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"e_1_2_4_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20503"},{"key":"e_1_2_4_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00010-2"},{"key":"e_1_2_4_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.08.004"},{"key":"e_1_2_4_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.07.008"},{"key":"e_1_2_4_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"e_1_2_4_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930100024"},{"key":"e_1_2_4_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.004"},{"key":"e_1_2_4_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_4_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"e_1_2_4_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120111"},{"key":"e_1_2_4_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930100028"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.21720","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.21720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T05:21:06Z","timestamp":1696396866000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.21720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,24]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1002\/jgt.21720"],"URL":"https:\/\/doi.org\/10.1002\/jgt.21720","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,24]]}}}