Localized Erdős–Pósa Property for Binary Tree Subdivisions

Abstract

We show that subdivisions of binary trees satisfy a localized version of the Erdős–Pósa property. Our first result is that if a graph G contains no two disjoint subdivisions of a given binary tree B, then there exists a subgraph H of G isomorphic to a subdivision of B and a set X⊆V(H) such that G- X contains no subgraph isomorphic to a subdivision of B, and the size of X is bounded by an exponential function of |V(B)|. We then generalize this result to settings where G does not contain k vertex-disjoint subgraphs each isomorphic to a subdivision of B. In this case, we demonstrate the existence of a set X whose size depends on both |V(B)| and k, so that G- X is B-minor-free.