Strengthening Erdós-Pósa property for minor-closed graph classes

Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

Let H and G be graph classes. We say that H has the Erdós- 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ó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 G is any non-trivial minor-closed graph class.

Original languageEnglish (US)
Pages (from-to)235-240
Number of pages6
JournalJournal of Graph Theory
Volume66
Issue number3
DOIs
StatePublished - Mar 2011

Keywords

  • Erdós-pósa property
  • graph minors

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Strengthening Erdós-Pósa property for minor-closed graph classes'. Together they form a unique fingerprint.

Cite this