✦ LIBER ✦
Strengthening Erdös–Pósa property for minor-closed graph classes
✍ Scribed by Fedor V. Fomin; Saket Saurabh; Dimitrios M. Thilikos
- Publisher
- John Wiley and Sons
- Year
- 2010
- Tongue
- English
- Weight
- 86 KB
- Volume
- 66
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Let H and G be graph classes. We say that H has the Erd" os-Pósa property for G if for any graph G ∈ G, the minimum vertex covering of all H-subgraphs of G is bounded by a function f of the maximum packing of H-subgraphs in G (by H-subgraph of G we mean any subgraph of G that belongs to H). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92-114] proved that if H is the class of all graphs that can be contracted to a fixed planar graph H, then H has the Erd" os-Pósa