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 f(k) such that for each positive integer k, every graph either contains k vertex-disjoint circuits or it has a feedback vertex set of f(k) vertices that intersects every circuit. Furthermore, f(k) = O(k log k) in the sense of Big O notation. Because of this theorem, circuits are said to have the Erdős–Pósa property.

The theorem claims that for any finite number k there is an appropriate (least) value f(k), with the property that every graph with no k vertex-disjoint circuits all circuits can be covered by f(k) vertices. This generalized an unpublished result of Béla Bollobás, which states that f(2) = 3. Erdős & Pósa (1965) obtained the bounds c₁k log k < f(k) < c₂k log k for the general case. The result suggests that although there are infinitely many different graphs with no k disjoint circuits, they split into finitely many simply describable classes. For the case k = 2, Lovász (1965) gave a complete characterization. Voss (1969) proved f(3) = 6 and 9 ≤ f(4) ≤ 12.

Erdős–Pósa property

A family F of graphs or hypergraphs is defined to have the Erdős–Pósa property if there exists a function f: N → N such that for every (hyper-)graph G and every integer k one of the following is true:

• G contains k vertex-disjoint subgraphs each isomorphic to a graph in F; or
• G contains a vertex set C of size at most f(k) such that G − C has no subgraph isomorphic to a graph in F.

The definition is often phrased as follows. If one denotes by ν(G) the maximum number of vertex disjoint subgraphs of G isomorphic to a graph in F and by τ(G) the minimum number of vertices whose deletion from G leaves a graph without a subgraph isomorphic to a graph in F, then ν(G) ≤ f(τ(G)), for some function f: N → N not depending on G.

References