On the presence of disjoint subgraphs of a specified type

Abstract We say that a graph family ℱ has the Erdös‐Pósa property if there exists a function f ( k ) such that any graph G contains either k disjoint subgraphs each isomorphic to a member of ℱ, or contains a set S of at most f ( k ) vertices such that G — S contains no graph in ℱ. We derive a general sufficient condition for a family of graphs to have the Erdös‐Pósa property. In particular, for any fixed natural number m the collection of cycles of length divisible by m has the Erdös‐Pósa property. As a by‐product, we obtain a polynomially bounded algorithm for finding a cycle of length divisible by m . On the other hand, we describe a general class of planar graphs H such that a collection of subdivisions of H does not have the Erdös‐Pósa property. In fact, H may even be a tree.