2025/12/25 by Icey Siyi Ai, Ai, Icey Siyi, Maria Chudnovsky +3
Computer Science · Mathematics · #05B40 #05C70 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2512.21530
openalex publication_date 2025/12/25 · openalex created_date 2025/12/30 · openalex updated_date 2026/07/28
For a graph H, we say that H has the Erdős-Pósa property for subdivisions with function f, if for every graph G, either G contains (as a subgraph) k+1 pairwise disjoint subdivisions of H or there exists a set X⊆ G such that G∖ X contains no H-subdivision and |X|≤ f(k). We show that every H that has the \EP property for subdivision also satisfies a localized version of the \EP property, as follows. Let H be an n-vertex graph with m≥ 1 edges that has the Erdős-Pósa property for subdivisions with function f, and let G be a graph that does not contain k+1 disjoint subdivisions of H. We demonstrate the existence of a set of at most k vertex disjoint subdivisions of H in G such that in their union, we can find a set X with the property that G ∖ X contains no H-subdivision and |X| ≤ 2f(k)mk +k(m-n).