Improving the gap of Erdos-Pósa property for minor-closed graph classes

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

Research output: Contribution to conferencePaperpeer-review

Abstract

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). In his monograph "Graph Theory", R. Diestel proves 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 give an alternative proof of this result with a better (still exponential) bounding function. Our proof, for the case when G is some non-trivial minor-closed graph class, yields a low degree polynomial bounding function f. In particular f(k) = O(k1.5).

Original languageEnglish (US)
Pages2-6
Number of pages5
StatePublished - 2008
Event7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2008 - Gargnano, Italy
Duration: May 13 2008May 15 2008

Conference

Conference7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2008
Country/TerritoryItaly
CityGargnano
Period5/13/085/15/08

Keywords

  • Erdos-Pósa property
  • Graph covering
  • Graph packing
  • Treewidth

ASJC Scopus subject areas

  • Control and Optimization
  • Discrete Mathematics and Combinatorics

Fingerprint

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

Cite this