2013/05/31 by Jean‐Florent Raymond, Jean-Florent Raymond, Raymond, Jean-Florent +2 · 1 citation
Computer Science · Mathematics · #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory #acm:05C83 #cs.DM #math.CO #msc:05C83
paper · pdf · doi:10.48550/arxiv.1305.7376
openalex publication_date 2013/05/31 · arxiv created 2013/06/08 · arxiv updated 2013/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph H, we denote by \cal 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 fH such that every graph G, either contains k disjoint copies of graphs in \cal M(H), or contains a set of fH(k) vertices meeting every subgraph of G that belongs in \cal 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 fH(k) = 2O(h2)⋅ k2⋅ 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 2O(h2)⋅ k2⋅ log k. We finally prove that the exponential dependence on h in these bounds can be avoided if H=K2,r. In particular, we show that f_K2,r=O(r2⋅ k2)