Erdős–Pósa theorem


In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, states that there is a function such that for each positive integer, every graph either contains at least vertex-disjoint cycles or it has a feedback vertex set of at most vertices that intersects every cycle. Furthermore, in the sense of Big O notation. Because of this theorem, cycles are said to have the [|Erdős–Pósa property].
The theorem claims that for any finite number there is an appropriate value, with the property that in every graph without a set of vertex-disjoint cycles, all cycles can be covered by no more than vertices. This generalized an unpublished result of Béla Bollobás, which states that. obtained the bounds for the general case. For the case, gave a complete characterization. proved and.

Erdős–Pósa property

A family of graphs or hypergraphs is defined to have the Erdős–Pósa property if there exists a function such that for every graph and every integer one of the following is true:
The definition is often phrased as follows. If one denotes by the maximum number of vertex disjoint subgraphs of isomorphic to a graph in and by the minimum number of vertices whose deletion from leaves a graph without a subgraph isomorphic to a graph in, then, for some function not depending on.
Rephrased in this terminology, the Erdős–Pósa theorem states that the family consisting of all cycles has the Erdős–Pósa property, with bounding function. Robertson and Seymour generalized this considerably. Given a graph, let denote the family of all graphs that contain as a minor. As a corollary of their grid minor theorem, Robertson and Seymour proved that has the Erdős–Pósa property if and only if is a planar graph. Moreover, it is now known that the corresponding bounding function is if is a forest, while for every other planar graph . The special case where is a triangle is equivalent to the Erdős–Pósa theorem.