Polynomial Gap Extensions of the Erdős-Pósa Theorem

Abstract

Given a graph $H$, we denote by $\mathcal{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$ such that every graph $G$, either contains $k$ disjoint copies of graphs in $\mathcal{M}(H)$, or contains a set of $f_H(k)$ vertices meeting every subgraph of $G$ that belongs in $\mathcal{M}(H)$. In this paper we prove that this is the case for every graph $H$ of pathwidth at most 2 and, in particular, that $f_H(k)=2^{O(h^2)}\cdot k^2\cdot \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 $2^{O(h^2)}\cdot k^2\cdot \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_{K_{2,r}}=O(r^2\cdot k^2)$