Erdös-Pósa property of minor-models with prescribed vertex sets

Abstract

A minor-model of a graph $H$ in a graph $G$ is a subgraph of $G$ that can be contracted to $H$. We prove that for a positive integer $\ell$ and a non-empty planar graph $H$ with at least $\ell -1$ connected components, there exists a function $f_{H,\ell }:\mathbb{N}\to \mathbb{R}$ satisfying the property that every graph $G$ with a family of vertex subsets $Z_1,\dots ,Z_m$ contains either $k$ pairwise vertex-disjoint minor-models of $H$ each intersecting at least $\ell$ sets among prescribed vertex sets, or a vertex subset of size at most $f_{H,\ell }(k)$ that meets all such minor-models of $H$. This function $f_{H,\ell }$ is independent with the number $m$ of given sets, and thus, our result generalizes Mader's $\mathcal{S}$-path Theorem, by applying $\ell =2$ and $H$ to be the one-vertex graph. We prove that such a function $f_{H,\ell }$ does not exist if $H$ consists of at most $\ell -2$ connected components.

29 pages, 4 figures; minor fix

References in corpus (1)

• Finding Detours is Fixed-parameter Tractable