A tight Erdős-Pósa function for planar minors

Let \(F\) be a family of graphs. Then for every graph \(G\) the maximum number of disjoint subgraphs of \(G\), each isomorphic to a member of \(F\), is at most the minimum size of a set of vertices that intersects every subgraph of \(G\) isomorphic to a member of \(F\). We say that \(F\) packs if equality holds for every graph \(G\). Only very few families pack.

As the next best weakening we say that \(F\) has the Erdős-Pósa property if there exists a function \(f\) such that for every graph \(G\) and integer \(k>0\) the graph \(G\) has either \(k\) disjoint subgraphs each isomorphic to a member of \(F\) or a set of at most \(f(k)\) vertices that intersects every subgraph of \(G\) isomorphic to a member of \(F\).

The name is motivated by a classical 1965 result of Erdős and Pósa stating that for every graph \(G\) and integer \(k>0\) the graph \(G\) has either \(k\) disjoint cycles or a set of \(O(k\log k)\) vertices that intersects every cycle. Thus the family of all cycles has the Erdős-Pósa property with \(f(k)=O(k\log k)\). In contrast, the family of odd cycles fails to have the Erdős-Pósa property. For every integer \(\ell\), a sufficiently large Escher Wall is a non-bipartite graph that has an embedding in the projective plane such that every face is even and every homotopically non-trivial closed curve intersects the graph at least \(\ell\) times. In particular, it contains no set of strictly less than \(\ell\) vertices such that each odd cycle contains at least one them, yet it has no two disjoint odd cycles.

By now there is a large body of literature proving that various families \(F\) have the Erdős-Pósa property. A very general theorem of Robertson and Seymour says that for every planar graph \(H\) the family \(F(H)\) of all graphs with a minor isomorphic to \(H\) has the Erdős-Pósa property. (When \(H\) is non-planar, \(F(H)\) does not have the Erdős-Pósa property.) The present paper proves that for every planar graph \(H\) the family \(F(H)\) has the Erdős-Pósa property with \(f(k)=O(k\log k)\), which is asymptotically best possible for every graph \(H\) with at least one cycle.