Erdős–Pósa theorem
 | This article needs attention from an expert in Mathematics. The specific problem is: Diagrams might help here rather than "big scary words". (June 2020) |
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 at least k vertex-disjoint cycles or it has a feedback vertex set of at most f(k) vertices that intersects every cycle. Furthermore, f(k) = Θ(k log k) 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 k there is an appropriate (least) value f(k), with the property that in every graph without a set of k vertex-disjoint cycles, all cycles can be covered by no more than 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. 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: ℕ → ℕ 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: ℕ → ℕ not depending on G.
Rephrased in this terminology, the Erdős–Pósa theorem states that the family F consisting of all cycles has the Erdős–Pósa property, with bounding function f(k) = Θ(k log k). Robertson and Seymour (1986) generalized this considerably. Given a graph H, let F(H) denote the family of all graphs that contain H as a minor. As a corollary of their grid minor theorem, Robertson and Seymour proved that F(H) has the Erdős–Pósa property if and only if H is a planar graph. Moreover, it is now known that the corresponding bounding function is f(k) = Θ(k) if H is a forest (Fiorini, Joret & Wood 2013), while f(k) = Θ(k log k) for every other planar graph H (Cames van Batenburg et al. 2019). The special case where H is a triangle is equivalent to the Erdős–Pósa theorem.
References
- Erdős, Paul; Pósa, Lajos (1965). "On independent circuits contained in a graph". Canadian Journal of Mathematics. 17: 347–352. doi:10.4153/CJM-1965-035-8.
{{cite journal}}: Invalid|ref=harv(help) - Robertson, Neil; Seymour, Paul (1986). "Graph minors. V. Excluding a planar graph". Journal of Combinatorial Theory, Series B. 41: 92–114. doi:10.1016/0095-8956(86)90030-4.
{{cite journal}}: Invalid|ref=harv(help) - 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.
{{cite journal}}: Invalid|ref=harv(help) - Lovász, László (1965). "On graphs not containing independent circuits". Mat. Lapok. 16: 289–299.
{{cite journal}}: Invalid|ref=harv(help) - Cames van Batenburg, Wouter; Huynh, Tony; Joret, Gwenaël; Raymond, Jean-Florent (2019). "A tight Erdős-Pósa function for planar minors". Advances in Combinatorics. 2: 33pp. doi:10.19086/aic.10807.
{{cite journal}}: Invalid|ref=harv(help) - Fiorini, Samuel; Joret, Gwenaël; Wood, David R. (2013). "Excluded Forest Minors and the Erdős–Pósa Property". Combinatorics, Probability and Computing. 22 (5): 700–721. arXiv:1204.5192. doi:10.1017/S0963548313000266.
{{cite journal}}: Invalid|ref=harv(help)