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 at least $k$ vertex-disjoint cycles or it has a feedback vertex set of at most $f (k)$ vertices. 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 $c 1 k log k < f (k) < c 2 k 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 \leq f (4) \leq 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:\mathbb {N} \rightarrow \mathbb {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) \leq f (ν (G))$ , for some function $f:\mathbb {N} \rightarrow \mathbb {N}$ 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.
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.
Voss, Heinz-Jürgen (1969). "Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten". Mathematische Nachrichten. 40 (1–3): 19–25. doi:10.1002/mana.19690400104.
Lovász, László (1965). "On graphs not containing independent circuits". Mat. Lapok. 16: 289–299.
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.
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. S2CID 122708.

Erdős–Pósa theorem

Erdős–Pósa property[]

References[]

See also[]