pith. sign in

arxiv: 1904.00879 · v2 · pith:TBR6B33Nnew · submitted 2019-04-01 · 🧮 math.CO

Erd\"os-P\'osa property of minor-models with prescribed vertex sets

classification 🧮 math.CO
keywords graphsetsvertexfunctionminor-modelscomponentsconnectedleast
0
0 comments X
read the original 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}\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 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Colorful Minors

    math.CO 2025-07 unverdicted novelty 7.0

    Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone p...