Strengthening Erdös–Pósa property for minor‐closed graph classes |
| |
| Authors: | Fedor V Fomin Saket Saurabh Dimitrios M Thilikos |
| |
| Institution: | 1. Department of Informatics, University of Bergen Po Box 7800, 5020, Bergen, Norway;2. The Institute of Mathematical Sciences Cit Campus, Chennai, India;3. Department of Mathematics National and Kapodistrian University of Athens Panepistimioupolis, Gr15784 Athens, Greece |
| |
| 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 G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that 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 |
| |
| Keywords: | Erdő s– pó sa property graph minors |
|
|
