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}rightarrow mathbb{R}$ satisfying the property that every graph $G$ with a family of vertex subsets $Z_1, ldots, 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 Maders $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.
تحميل البحث