A tight Erdős-Pósa function for planar minors
- Département d'Informatique, Université libre de Bruxelles
- ORCID iD: 0000-0001-8631-6222
- Département d'Informatique, Université libre de Bruxelles
- ORCID iD: 0000-0002-6908-923X
- Département d'Informatique, Université libre de Bruxelles
- ORCID iD: 0000-0002-7157-6694
- TU Berlin
- ORCID iD: 0000-0003-4646-7602
Editorial introduction
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(klogk) vertices that intersects every cycle. Thus the family of all cycles has the Erdős-Pósa property with f(k)=O(klogk). In contrast, the family of odd cycles fails to have the Erdős-Pósa property. For every integer ℓ, 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 ℓ times. In particular, it contains no set of strictly less than ℓ 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(klogk), which is asymptotically best possible for every graph H with at least one cycle.