1. Strengthening Erdös–Pósa property for minor‐closed graph classes
- Author
-
Fomin, Fedor V., Saurabh, Saket, and Thilikos, Dimitrios M.
- Abstract
Let ℋ︁ and 𝒢 be graph classes. We say that ℋ︁ has the Erdős–Pósa property for 𝒢 if for any graph G∈𝒢, the minimum vertex covering of all ℋ︁‐subgraphs of Gis bounded by a function fof the maximum packing of ℋ︁‐subgraphs in G(by ℋ︁‐subgraph of Gwe mean any subgraph of Gthat belongs to ℋ︁). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ℋ︁ is the class of all graphs that can be contracted to a fixed planar graph H, then ℋ︁ has the Erdős–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when 𝒢 is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011 more...
- Published
- 2011
- Full Text
- View/download PDF