2019/04/01 by O‐joung Kwon, Dániel Marx, Kwon, O-joung +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1904.00879
openalex publication_date 2019/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℓ and a non-empty planar graph H with at least ℓ-1 connected components, there exists a function fH, ℓ:ℕ→ ℝ satisfying the property that every graph G with a family of vertex subsets Z1, …, Zm contains either k pairwise vertex-disjoint minor-models of H each intersecting at least ℓ sets among prescribed vertex sets, or a vertex subset of size at most fH, ℓ(k) that meets all such minor-models of H. This function fH, ℓ is independent with the number m of given sets, and thus, our result generalizes Mader's \mathcal S-path Theorem, by applying ℓ=2 and H to be the one-vertex graph. We prove that such a function fH, ℓ does not exist if H consists of at most ℓ-2 connected components.