The Erdös-Pósa property

Abstract

Cycles obey a packing-covering duality, as Erdös and Pósa proved in their now classic 1965 paper: every graph contains k disjoint cycles, or a vertex set of size O(k⋅log(k)) that meets every cycle. More succinctly, we might say that cycles have the vertex-Erdös-Pósa property. Here, a class of graphs has the vertex-Erdös-Pósa property if there is a function f: N → N such that in every graph there are either k vertex-disjoint subgraphs belonging to the class or a vertex set X of size |X| ≤ f(k) that intersects all subgraphs that lie in the class. Probably the most famous result in this field, after the theorem by Erdös and Pósa, is due to Robertson and Seymour. They showed that the set of expansions of a fixed graph H has the vertex-Erdös-Pósa property if and only if H is planar. In particular, this implies that the cycles have the vertex-Erdös-Pósa property. One of the main results of this work is a generalization of the theorem by Robertson and Seymour to labelled graphs. Gallai proved that A-paths, that is for a vertex set A in a graph, paths with distinct endvertices in A that are otherwise disjoint from A, have the vertex-Erdös-Pósa property. Bruhn, Heinlein and Joos showed that the A-paths of length equivalent to 0 mod m have the vertex-Erdös-Pósa property if m=2 and they do not have it if m is a non-prime integer such that m≠4. Then Bruhn et al. asked whether such paths have the vertex-Erdös-Pósa property when m=4 or when m is an odd prime. In this work, it will be proven that such paths have the vertex-Erdös-Pósa property when m=4. A more general result will be proven as well. To that end, let the edges of a graph G be weighted with elements of an abelian group Γ. We say that a path P in G is zero (with respect to Γ) if the sum of the weights of the edges of P is 0 ∈ Γ, where 0 is the neutral element of Γ. The groups for which the zero A-paths have the vertex-Erdös-Pósa property will be characterized, which also answers the question by Bruhn et al. for odd primes m. When we replace ''vertex/vertices'' by ''edge/edges'' in the definition of the vertex-Erdös-Pósa property, we obtain the edge-Erdös-Pósa property. Generally, much less is known about the edge-Erdös-Pósa property than about the vertex-Erdös-Pósa property. In particular, there is no edge-equivalent of the theorem by Robertson and Seymour. In this work, it will be shown that expansions of the house graph, the ladder with three rungs as well as long cycles have the edge-Erdös-Pósa property (these graphs will be defined later). None of these are new results, however, the proofs obtained are simpler and with a slightly better bound on the size of an edge set that intersects all the corresponding graphs. Lastly, it will be proven that A--B-paths, that is for vertex sets A,B in a graph, paths with one endvertex in A and one in B that are otherwise disjoint from both A and B, of some minimum length have the edge-Erdös-Pósa property.