Quadratic Upper Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, Saket Saurabh · Journal of Graph Theory · 2013
Abstract According to the classical Erdős–Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most vertices that hits all its cycles. Robertson and Seymour (J Comb Theory Ser B 41 (1986), 92–114) generalized this result in the best possible way. More specifically, they showed that if is the class of all graphs that can be contracted to a fixed planar graph H, then every graph G either contains a set of k vertex‐disjoint subgraphs of G, such that each of these subgraphs is isomorphic to some graph in or there exists a set S of at most vertices such that contains no subgraph isomorphic to any graph in . However, the function f is exponential. In this note, we prove that this function becomes quadratic when consists all graphs that can be contracted to a fixed planar graph . For a fixed c, is the graph with two vertices and parallel edges. Observe that for this corresponds to the classical Erdős–Pósa theorem.