Polynomial gap extensions of the Erdős-Pósa theorem
Jean‐Florent Raymond, Dimitrios M. Thilikos · Scuola Normale Superiore eBooks · 2013
Given a graph H, we denote by M(H) all graphs that can be contracted to H. The following extension of the Erdős-Pósa Theorem holds:for every h-vertex planar graph H, there exists a function f H: N → N such that every graph G, either contains k disjoint copies of graphs in M(H), or contains a set of f H(k) vertices meeting every subgraph of G that belongs in M(H). In this paper we prove that f H can be polynomially (upper) bounded for every graph H of pathwidth at most 2 and, in particular, that f H(k) = 2o(h 2). k 2. log k. As a main ingredient of the proof of our result, we show that for every graph H on h vertices and pathwidth at most 2, either G contains k disjoint copies of H as a minor or the treewidth of G is upper-bounded by 2o(h) 2. k 2. log k. We finally prove that the exponential dependence on h in these bounds can be avoided if H = K 2,r. In particular, we show that f K2,r = O (r 2. k 2).