Erdős–Pósa theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 in 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 c1k log k < f(k) < c2k 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[edit]

A family F of graphs or hypergraphs is defined to have the Erdős–Pósa property if there exists a function f: NN 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 GC 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: NN not depending on G.

References[edit]

  • Erdős, Paul; Pósa, Lajos (1965). "On independent circuits contained in a graph". Canad. Journ. Math. 17: 347–352. doi:10.4153/CJM-1965-035-8.
  • Voss, Heinz-Jürgen (1969). "Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten". Mathematische Nachrichten. 40: 19–25. doi:10.1002/mana.19690400104.
  • Lovász, László (1965). "On graphs not containing independent circuits". Mat. Lapok. 16: 289–299.