# Dynamic Erdős-Pósa listing

Note that the papers listed on this page have not all been peer-reviewed (yet). All of them are availlable online or have been published in a journal or conference proceedings with peer-review.
If you notice a missing result, a typo, a broken link, or an outdated reference, please contact me and I will update the list.

MathJax is used for rendering formulas, so you need to have JavaScript enabled in order to see them.

### Basic definitions

Let $\mathcal{H}$ be a class of graphs and let $G$ be a graph.

• An $\mathcal{H}$-vertex-packing in $G$ is a collection of vertex-disjoint subgraphs of $G$, each isomorphic to a member of $\mathcal{H}$.
• An $\mathcal{H}$-vertex-cover in $G$ is a set $X$ of vertices of $G$ such that $G\setminus X$ has no subgraph isomorphic to a member of $\mathcal{H}$.

Let $\mathcal{G}$ be a class of graphs. We say that $\mathcal{H}$ (refered to as the guest class) has the vertex-Erdős–Pósa property in the class $\mathcal{G}$ (the host class) with gap $f$ if, for every $G \in \mathcal{G}$ and $k \in \mathbb{N}$,

• either $G$ has an $\mathcal{H}$-vertex-packing of size $k+1$;
• or $G$ has a $\mathcal{H}$-vertex-covering of size $f(k)$.

The notions of $\mathcal{H}$-edge-packing, $\mathcal{H}$-edge-cover, and edge-Erdős–Pósa property can be defined similarly by replacing “vertex” by “edge” in the definitions above.

Notice that a different definition of the gap (with $k+1$ replaced by $k$ above) is sometimes used in the litterature (but not on this page), leading to slightly different values of the gap.

The fourth column (T.) of the tables below refers to the type of Erdős–Pósa property: v for vertex and e for edge. The definitions of the other variants of the Erdős–Pósa property mentioned below (w for weighted, v1/2 for vertex half-integral, etc.) are not given here but can be found in the corresponding papers.

Notation of the type $O_t(k)$ and $o_t(k)$ is used to stress that the hidden constants depend on $t$.

## Positive results

### Acyclic patterns

Ref. Guest class Host class T. Gap at most Remarks
[Kőn31] $K_2$ bipartite v $k$
[LY78] directed cuts any digraph e $k$
[Lov76] directed cuts any digraph e $k$
[Men27] $(S,T)$-paths any v/e $k$
[MNL84] $(S,T)$-paths of length $\geq t$ any v $(3(t + 2) - 5)k$
[HU19] $(S,T)$-paths of length $\geq t$ any e unspecified
[Grü38] directed $(S,T)$-paths any digraph v/e $k$
[Gal64] any v $2k$
[GV95] , $S$ independent graphs where every block has $\leq 2$ cutvertices and is either a cycle or a clique v $k$
[Sam92] , $S$ independent unicyclic graphs whose cycle has $\leq 2$ vertices of degree $\geq 3$ v $k$
[Sam83] [TV89] , $S$ independent trees v $k$
[KKKX20] any v $k$
[Mad78b] any v unspecified see [Sch01]
[Mad78a] any e $2k$ see [SS04], [BHJ18a]
[HU19] of length $\geq t$ any e unspecified
[GGR+09] odd any v $2k$
[BHJ18a] of length at least $t$ any v $4kt$
[HU19] of length $\geq t$ any e unspecified
[BHJ18a] even any v $10k$
[BU18] of length $0 \mod 4$ any v unspecified
[BU18] of length $2 \mod 4$ any v unspecified
[Ulm20] $S$-paths of length $0 \mod m$, where $m$ is an odd prime any v unspecified
[Ulm20] $S$-paths of length $d \mod m$ if $\forall x,y \in \{0, \dots, m-1\}, y \neq 0 \Rightarrow \exists n \in \mathbb{Z}, 2x+ny = d \mod m$ any v unspecified
[CGG+06] $S$-paths edge-group-labeled digraphs v $2k$
[Wol10] $S$-paths edge-group-labeled graphs v $50 k^4$
[Ulm20] zero $S$-paths graphs whose edges are labeled by a finite abelian group v unspecified
[Ulm20] $S$-paths of length $\geq t$ and value $\gamma$, where $\gamma \in \Gamma$ graphs whose edges are labeled by an abelian group $\Gamma$ such that $\forall x,y \in \Gamma, y \neq 0 \Rightarrow \exists n \in \mathbb{Z}, 2x + ny = \gamma$ v unspecified
[IS17] any e $2k+1$
[MW15] $H$-valid paths, $H$ with no matching of size $t$ any v $2^{2^{O(k+t)}}$
[FJW13] $\mathcal{M}(H)$, $H$ forest any v $O_{H}(k)$
[BHJ18a] any v $4kt$
[SU20] any e $2t^2k^2$

### Triangles

The following table contains results related to Tuza’s conjecture, that can be seen as Erdős-Pósa type problems.

Ref. Guest class Host class T. Gap at most
[Tuz90] triangles planar graphs e $2k$
[Tuz90] triangles graphs with $m \geq 7n^2/16$ e $2k$
[Tuz90] triangles tripartite graphs e $7k/3$
[Kri95] triangles -free graphs e $2k$
[HK88] triangles tripartite graphs e $1.956k$
[Hax99] triangles any e $(3-\frac{3}{23})k$
[ALBT11] triangles odd-wheel-free graphs e $2k$
[ALBT11] triangles 4-colorable graphs e $2k$
[HKT11] triangles $K_4$-free planar graphs e $3k/2$
[HKT11] triangles $K_4$-free graphs e $3k/2$
[Pul15] triangles graphs with $\mathrm{mad} < 7$ e $2k$
[LBT16] triangles graphs whose is perfect e $2k$
[Tuz94] directed triangles planar oriented graphs e $k$
[MPT18] directed triangles directed graphs e $2k-1$

### Cycles

For cycles with length or modularity constraints or using prescribed vertices ($S$-cycles), see the next tables.

Ref. Guest class Host class T. Gap at most Remarks
[Lov65] cycles graphs without 2 vertex-disjoint cycles v =3
[Vos69] cycles graphs without 3 vertex-disjoint cycles v =6
[Vos67] cycles graphs without 4 vertex-disjoint cycles v 12 see [Vos69]
[EP65] cycles any v $O(k\log k)$
[Sim67] cycles any v $\left (4 + o(1)\right )k \log k$
[Vos69] cycles any v $\left (2 + o(1) \right )k \log k$
[Vos69] cycles any v $4k \left (1+ \log \left (k + \frac{3}{2} \right ) \right)$
see [Die05] cycles any e $(2 + o(1))k \log k$
[DZ02] cycles weighted graphs with no induced subdivision of $K_{2,3}$, a wheel, or an w $k$
[DXZ03] cycles graphs with no induced subdivision of $K_{3,3}$, a wheel, or an v $k$
[BD92] cycles planar graphs v $54k$
[KLL02] cycles planar graphs v $5k$
[CHC12] [MYZ13][CGH14] cycles planar graphs v $3k$
[CGH14] cycles graphs that embed in a closed surface of Euler characteristic $\geq 0$ v $3k$
[CGH14] cycles graphs that embed in a closed surface of Euler characteristic $c \leq 0$ v $3k - 103c$
[KLL02] cycles outerplanar graphs v $2k$
[Mun16] cycles $(K_4, \text{claw}, \text{diamond})$-free graphs v $2k$
[Mun16] cycles planar claw-free graphs with $\Delta\leq 4$ v $2k$
[BDM+19] cycles planar subcubic graphs v $2k$
[MYZ13] cycles planar graphs e $4k-1$
[BD92] faces plane graphs v $27k$
[BD92] + [MYZ13] faces plane graphs v $6k$
[BD92] + [MYZ13] + [GR09] connected planar graphs with $\delta \geq 3$ v $66k - 14$ the cover additionally induces a connected subgraph
[RRST96] directed cycles any digraph v unspecified
[MMP+19] directed cycles any digraph v1/4 $O(k^4)$
[MMP+19] directed cycles any digraph v1/2 $O(k^6)$
[RS96] directed cycles planar digraphs v $O(k\log(k)\log\log k)$
[RS96] + [GW96] directed cycles planar digraphs v $63k$
[STV22] directed cycles planar digraphs v $12k$
[GT11] directed cycles v $k$
[GT11] directed cycles digraphs with no isomorphic to an or v $k$
[LY78] directed cycles planar digraphs e $k$
[Sey96] directed cycles eulerian digraphs with a linkless embedding in 3-space e $k$
[HJW18] cycles non homologous to zero embedded graphs v1/2 unspecified
[STV22] any collection of uncrossable cycles planar graphs or planar digraphs v $12k$
[STV22] any collection of uncrossable cycles planar graphs or planar digraphs e $9.6k$

### Cycles with length constraints

Includes cycles of a certain value with respect to a labeling of the edges or vertices of the graph.

Ref. Guest class Host class T. Gap at most Remarks
[Ree99] odd cycles planar graphs v superexponential
[FHRV06] odd cycles planar graphs v $10k$
[KSS12] odd cycles planar graphs v $\max(0, 6k-2)$
[Tho01] odd cycles $2^{3^{9k}}$-connected graphs v $2k$
[RR01] odd cycles $576k$-connected graphs v $2k$
[KR09] odd cycles $24k$-connected graphs v $2k$
[Ree99] odd cycles graphs v unspecified
[KN07] odd cycles embeddable in an orientable surface of Euler genus $t$ v/e unspecified
[BR00] odd cycles planar e unspecified
[KV04] [FHRV06] odd cycles planar graphs e $2k$
[KK16] odd cycles 4-edge-connected graphs e $2^{2^{O(k \log k)}}$
[Ree99] odd cycles any v1/2 unspecified
[BHJ18a] even cycles any e
[CJU19] even cycles any e $O(k \log k)$
[Tho88] cycles of length $0 \mod t$ any v $2^{t^{O(k)}}$
[CC13] cycles of length $0 \mod t$ any v $k~ \mathrm{polylog}~k \cdot 2^{\mathrm{poly}(t)}$
[CHJR18] cycles of length $0 \mod t$ any v $O_t(k \log k)$
[CHJR18] cycles of length $0 \mod t$ any proper minor-closed class $\mathcal{F}$ v $O_{t,\mathcal{F}}(k)$
[KW06] non-zero cycles $(15k/2)$-connected group-labeled graphs v $2k$
[Wol11] non-zero cycles group-labeled graphs, c.f. [Wol11] v $c^{k^{c’}}$ for some $c,c’$
[Wol11] cycles of non-zero length mod $2t+1$ any v $c^{k^{c’}}$ for some $c,c’$
[HJW18] doubly non-zero cycles, c.f. [HJW18] doubly group-labeled graphs v1/2 unspecified
[HJW18] odd cycles non homologous to zero embedded graphs v1/2 unspecified
[GHK+21] cycles belonging to certain $\mathbb{Z}_2$-homotopy classes of $\Sigma$ graphs embedded on a surface $\Sigma$ v1/2 unspecified
[GHK+21] cycles whose equals a certain value graphs whose edges are labeled by a finite abelian group v1/2 unspecified
[GHK+21] cycles whose avoid a graphs whose edges are labeled with finitely many abelian groups v1/2 unspecified besides $k$, the gap only depends on the number of groups and of values to avoid
[GHK+21] cycles whose avoid a graphs whose vertices are labeled with finitely many abelian groups v1/2 unspecified besides $k$, the gap only depends on the number of groups and of values to avoid
[Bir03] cycles of length $\geq 4$ graphs without 2 vertex-disjoint cycles of length $\geq 4$ v =4
[Bir03] cycles of length $\geq 5$ graphs without 2 vertex-disjoint cycles of length $\geq 5$ v =5
[BBR07] cycles of length $\geq t$ any v $(13+o_t(1))tk^2$
[FH14] cycles of length $\geq t$ any v $(6t+4+o_t(1))k\log k$
[MNŠW17] cycles of length $\geq t$ any v $6kt + (10 + o(1)) k \log k$
[BHJ16] cycles of length $\geq t$ any e $O(k^2 \log k + kt)$
[CJU19] cycles of length $\geq t$ any e $8k(t−1)(\log_2(kt) + 1)$
[KKKX20] directed odd cycles any digraph v1/2 unspecified
[HM13] directed cycles of length $\geq 3$ any digraph v unspecified
[AKKW16] directed cycles of length $\geq t$ any digraph v unspecified

### Cycles with prescribed vertices or edges

For a set $S \subseteq V(G)$, an $S$-cycle of $G$ is a cycle of $G$ containing at least one vertex of $S$. The results listed in this section relate, for any $S \subseteq V(G)$, the maximum number of $S$-cycles with the minimum number of vertices whose removal destroys all $S$-cycles. This setting extends to cycles that of $S$-paths mentioned in the acyclic patterns section.

Ref. Guest class Host class T. Gap at most Remarks
[KKM11] $S$-cycles any v $40k^2 \log k$
[PW12] $S$-cycles any v/e $O(k \log k)$
[KKL19] $S$-cycles graphs without two vertex-disjoint $S$-cycles v =4
[BJS17] $S$-cycles of length at least $t$ any v $O(tk\log k)$
[Joo14] odd $S$-cycles $50k$-connected graphs v $O(k)$
[KK13] odd $S$-cycles any v1/2 unspecified
[Bru19] even $S$-cycles any e unspecified
[KK12] directed $S$-cycles all digraphs v1/5 unspecified
[KKKK13] odd directed $S$-cycles any digraph v1/2 unspecified
[HJW18] any v unspecified
[GHK+21] cycles that intersect at least $t_i\leq t$ times the set $S_i$ for every $i \in \{1, \dots, m\}$, for a collection $S_1, \dots, S_m$ of subsets of vertices of the graph any v1/2 unspecified besides $k$, the gap only depends on $m$ and $t$
[STV22] planar graphs v 12

### Minors

For every graph $H$, we denote by $\mathcal{M}(H)$ the class of graphs that can be contracted to~$H$. (So $H$ is a minor of $G$ iff some subgraph of $G$ is isomorphic to a graph in $\mathcal{M}(H)$.) For every digraph $D$, we denote by $\vec{\mathcal{M}}_b(D)$ (respectively $\vec{\mathcal{M}}_s(D)$) the class of all digraphs that contain $D$ as a butterfly contraction (respectively strong contraction).

For every $t \in \mathbb{N}$, $\theta_t$ is the multigraph with two vertices connected by one edge of multiplicity $t$. For every $t\in \mathbb{N}$, a digraph is said to be $t$-semicomplete if for every vertex $v$ there are at most $t$ vertices that are not connected to $v$ by an arc (in either direction). A semicomplete digraph is a 0-semicomplete digraph.

Ref. Guest class Host class T. Gap at most
[Sim67] $\mathcal{M}($complement of ($K_{3,3}$ minus an edge)) any v $(4000+o(1))k \log k$
[RS86] $\mathcal{M}(H)$, $H$ planar any v unspecified
[RS86] $\mathcal{M}(H)$, $H$ planar with $q$ connected components ${G, \mathbf{tw}(G)\leq t}$ v $(t-1)(kq-1)$
[FST11] $\mathcal{M}(H)$, $H$ planar connected any proper minor-closed class $\mathcal{F}$ v $O_{H,\mathcal{F}}(k)$
[DKW12] $\mathcal{M}(K_t)$ $O(kt)$-connected graphs v unspecified
[FLM+13] $\mathcal{M}(\theta_t)$ any v $O(t^2k^2)$
[RT13] $\mathcal{M}(H), \mathbf{pw}(H) \leq 2$ and $H$ connected on $h$ vertices any v $2^{O(h^2)}\cdot k^2\log k$
[CC13] + [CC14] $\mathcal{M}(H)$, $H$ planar connected on $h$ vertices any v $\mathrm{poly}(h)\cdot k\cdot \mathrm{polylog}~k$
[RST16] $\mathcal{M}(\theta_t)$ any e $k^2t^2 \mathrm{polylog}~kt$
[RST16] $\mathcal{M}(\theta_t)$ any e $k^4t^2 \mathrm{polylog}~kt$
[SU20] $\mathcal{M}(H)$ where $H$ is the $2 \times 3$ grid any e $O(k^3 \log k)$
[SU20] $\mathcal{M}(\text{house graph})$ any e $O(k^2 \log k)$
[AKKW16] $\vec{\mathcal{M}}_{b}(H)$, $H$ is a butterfly minor of a any digraph v unspecified
[CRST17] $\mathcal{M}(H)$, $H$ connected ${G, \mathbf{tpw}(G) \leq t}$ v/e $O_{H,t}(k)$
[CRST17] $\mathcal{M}(\theta_t)$ any v/e $O_t(k\log k)$
[CRST17] simple graphs e unspecified
[BH17] $\mathcal{M}(K_4)$ any e $O(k^8 \log k)$
[AFH+17] , $t \in \mathbb{N}$ any v $O_t(k \log k)$
[Ray18] tournaments v unspecified
[Ray18] $\vec{\mathcal{M}}_{b}(H)$, $H$ strongly-connected tournaments v unspecified
[CHJR18] $\mathcal{M}(H)$, $H$ planar any v $O_H(k \log k)$
[BJS18] $\mathcal{M}(H)$, when $H$ belongs to a of labelled 2-connected planar graphs any v unspecified
[KM19] graphs of $\mathcal{M}(H)$ meeting $\geq \ell$ of the prescribed subsets, for $\ell \in \mathbb{N}_{\geq 1}$ and $H$ a planar graph with $\geq \ell-1$ connected components () any graph with prescribed subsets v unspecified

### Topological minors

For every graph $H$, we denote by $\mathcal{T}(H)$ the class of graphs that contain $H$ as a topological minor. For every digraph $D$, we denote by $\vec{\mathcal{T}}(D)$ the class of all digraphs that contain $D$ as a directed topological minors.

Let $H$ be a graph of maximum degree 3. As a graph $G$ contains $H$ as a minor iff it contains it as a topological minor, all the results stated in the previous section hold for topological minors if the guest graph has maximum degreee 3 (for instance $\mathcal{T}(H)$ has the Erdős-Pósa property for every planar $H$ with maximum degree 3, by [RS86]). These results are not restated here.

Ref. Guest class Host class T. Gap at most Remark
[Tho88] , $H$ connected planar subcubic any v unspecified
from [CC13] , $H$ connected planar subcubic any v $O_{H,t}(k~ \mathrm{polylog}~k)$
[CHJR18] , $H$ planar subcubic any v $O_{H,t}(k \log k)$
[CHJR18] , $H$ planar subcubic any proper minor-closed class $\mathcal{F}$ v $O_{H, \mathcal{F},t}(k)$
[AKKW16] $\vec{\mathcal{T}}(H)$, $H$ is a topological minor of a any digraph v unspecified
[Liu17] $\mathcal{T}(H)$ any v1/2 unspecified holds for rooted subdivisions
[Ray18] $\vec{\mathcal{T}}(H)$, $H$ strongly-connected tournaments v unspecified
[BP21] $\vec{\mathcal{T}}(H)$ tournaments v $O_H(k \log k)$

### Immersions

For every graph $H$, we denote by $\mathcal{I}(H)$ the class of graphs that contain $H$ as an immersion.

Ref. Guest class Host class T. Gap at most
[Liu15] $\mathcal{I}(H)$ 4-edge-connected e unspecified
[Liu15] any e1/2 unspecified
[GKRT17] $\mathcal{I}(H)$, $H$ planar subcubic connected on $h>0$ edges any e $\mathrm{poly}(h \cdot k)$
[GKRT17] $\mathcal{I}(H)$, $H$ connected on $h>0$ edges ${G, \mathbf{tcw}(G) \leq t}$ e $h \cdot t^2 \cdot k$
[GKRT17] $\mathcal{I}(H)$, $H$ connected on $h>0$ edges ${G, \mathbf{tpw}(G) \leq t}$ e $h \cdot t^2 \cdot k$
[KK18a] $\mathcal{I}(H)$ 4-edge-connected e unspecified
[Ray18] $\vec{\mathcal{I}}(H)$, $H$ strongly-connected tournaments e unspecified
[BP21] $\vec{\mathcal{I}}(H)$ tournaments e $O_H(k^3)$

### Induced patterns

In this setting, a $\mathcal{H}$-vertex-packing ($\mathcal{H}$-edge-packing) in $G$ is a collection of vertex-disjoint (edge-disjoint) induced subgraphs of $G$.

Ref. Guest class Host class T. Gap at most
[EP65] cycles of length $\geq 3$ any v $O(k\log k)$
[KK18b] cycles of length $\geq 4$ any v $O(k^2\log k)$
trivial $\mathcal{T}(H)$, $H$ linear forest any v $O(k)$
[ALM+18] {cycles of length $\geq 4$} $\cup$ {asteroidal triples} any v $O(k^2 \log k)$
[KR18] $\mathcal{T}(H)$, $H\in \{\text{diamond}, \text{1-pan}, \text{2-pan}\}$ any v $\mathrm{poly}(k)$
[Wei18] cycles of length $\geq t$ for $t \geq 3$ $K_{s,s}$-subgraph free graphs v unspecified

### Patterns with prescribed positions

The setting of the results in this section is slightly different: instead of packing/covering all possible occurences of a given pattern in a host graph, we focus on a given list of possible occurences. For instance, one can consider a family $\mathcal{F}$ of (non necessarily disjoint) subtrees of a tree $T$, and compare the maximum number of disjoint elements in $\mathcal{F}$ with the minimum number of vertices/edges of $T$ intersecting all elements of $\mathcal{F}$. This is stressed in the following table by refering to guest graphs with words related to substructures (like “subtrees”). Note that there may be two isomorphic subtrees $F,F’$ of $T$ such that $F \in \mathcal{F}$ and $F’ \not \in \mathcal{F}$.

For every positive integer $t$, a $t$-path is a disjoint union of $t$ paths, and a $t$-subpath of a $t$-path $G$ is a subgraph that has a connected intersection with every connected component of $G.$ The concepts of $t$-forests and $t$-subforests are defined similarly. We denote by $\textbf{cc}(G)$ the number of connected components of the graph $G$.

Ref. Guest class Host class T. Gap at most
[HS58] subpaths paths v $k$
[GL69] $t$-subpaths $t$-paths v $O(k^{t!})$
[GL69] subgraphs $H$ with $\textbf{cc}(H) \leq t$ paths v unspecified
[GL69] $t$-subforests $t$-forests v unspecified
[GL69] subtrees trees v $k$
[Kai97] $t$-subpaths $t$-paths v $(t^2-t+1)k$
[Alo98] $t$-subpaths $t$-paths v $2t^2k$
[Alo02] subgraphs $F$ with $\textbf{cc}(F) \leq t$ trees v $2t^2k$
[Alo02] subgraphs $H$ with $\textbf{cc}(H) \leq t$ ${G, \textbf{tw}(G)\leq w}$ v $2(w+1)t^2k$
[Tuz94] directed subtriangles planar oriented graphs e $k$

### Classes with bounded parameters

Some other results on classes with bounded parameters appear in other tables.

Ref. Guest class Host class T. Gap at most
[RS86] $\mathcal{M}(H)$, $H$ planar with $q$ connected components ${G, \mathbf{tw}(G)\leq t}$ v $(t-1)(kq-1)$
[Tho88] any family of connected graphs ${G, \mathbf{tw}(G)\leq t}$ v $k(t+1)$
[FJW13] ${H, \textbf{pw}(H) \geq t}$ any v $O_t(k)$
[GKRT17] $\mathcal{I}(H)$, $H$ connected on $h>0$ edges ${G, \mathbf{tcw}(G) \leq t}$ e $h \cdot t^2 \cdot k$
[GKRT17] $\mathcal{I}(H)$, $H$ connected on $h>0$ edges ${G, \mathbf{tpw}(G) \leq t}$ e $h \cdot t^2 \cdot k$
[CRST17] any finite family of connected graphs ${G, \textbf{tpw}(G) \leq t}$ v/e $O_{t}(k)$
[MMP+19] all digraphs with directed treewidth $\geq t$ any digraph v1/4 $\textrm{poly}(k,t)$

### Fractional packings

The results in this table relate the value of the (usual) packing / covering numbers with fractional packing / covering numbers (see the referenced papers for a definition).

Ref. Guest class Host class $\nu^*$ $\tau$ Relationship
[Sey95] directed cycles any digraph max fractional vertex packing min integral vertex covering $\tau \leq 4 \nu^* \ln(4 \nu^* ) \ln\log(4\nu^*)$

## Negative results

### Lower bounds for paths

Ref. Guest class Host class T. Gap at least
[MW15] $H$-valid paths, $H$ with no matching of size $t$ all graphs v unavoidable dependency in $t$
[BHJ18a] $S$-paths of length $p \mod t$, for $t>4$ composite and fixed $p \in \{0, \dots, t-1\}$ all graphs v/e arbitrary
[BU18] of length $1 \mod 4$ all graphs v arbitrary
[BU18] of length $3 \mod 4$ all graphs v arbitrary
[BHJ18a] odd/even all graphs v/e arbitrary
[BHJ18a] odd/even all graphs e arbitrary
[BHJ18a] of length $0 \mod 4$ all graphs e arbitrary
[BHJ18a] of length $0 \mod p$, for any prime $p$ all graphs e arbitrary
[IS17] all graphs e $\geq 2k+1$
[BHJ18a] all graphs e arbitrary
[BHJ18a] all digraphs v/e arbitrary
[BHJ18a] odd/even all digraphs v/e arbitrary

### Lower bounds for cycles

Ref. Guest class Host class T. Gap at least Remark
[Tuz90] triangles all graphs e $\geq 2k$
[Tuz90] directed triangles directed graphs without 3 edge-disjoint directed triangles e 3
[Lov65] cycles graphs without 2 vertex-disjoint cycles v =3
[Vos69] cycles graphs without 3 vertex-disjoint cycles v =6
[Vos67] cycles graphs without 4 vertex-disjoint cycles v $\geq 9$ see [Vos69]
[EP65] cycles all graphs v $\Omega(k \log k)$
[Sim67] cycles all graphs v $> \left (\frac{1}{2} + o(1) \right ) k \log k$
[Vos69] cycles all graphs v $\geq \frac{1}{8} k \log k$ see [Vos68]
[KLL02] cycles planar graphs v $\geq2k$
[MYZ13] cycles planar graphs e $\geq 4k-c$, $c\in \mathbb{R}$
[DNL87] [Ree99] odd cycles all graphs v arbitrary
[DNL87] cycles of length $p \mod t$, for every fixed $p \in \{1, \dots, t-1\}$ all graphs v arbitrary
[Ree99] odd cycles all graphs e arbitrary
[Tho01] odd cycles planar graphs v $\geq 2k$
[KV04] odd cycles planar graphs e $\geq 2k$
[PW12] $S$-cycles all graphs v $\Omega(k\log k)$
[KKL19] $S$-cycles graphs without two disjoint $S$-cycles v =4
[KK13] odd $S$-cycles all graphs v arbitrary
[Bru19] even $S$-cycles of length $\geq \ell$, for every fixed $\ell \geq 5$ all graphs e arbitrary
[Bru19] $S$-cycles of length $0 \mod t$, for every fixed $t > 2$ all graphs e arbitrary
[Sey95] directed cycles all digraphs $\frac{1}{30} k \ln k$
[GW96] directed cycles planar digraphs v $\frac{3}{2}k$ simpler: a $C_5$ where every edge is replaced by a directed triangle
[KK12] directed $S$-cycles all digraphs v/e arbitrary
[KKKK13] odd directed $S$-cycles all digraphs v arbitrary
[Bir03] cycles of length $\geq 4$ graphs without 2 vertex-disjoint cycles of length $\geq 4$ v =4
[Bir03] cycles of length $\geq 5$ graphs without 2 vertex-disjoint cycles of length $\geq 5$ v =5
[FH14] cycles of length $\geq t$ all graphs v $\Omega(k\log k)$, $t$ fixed
[FH14] cycles of length $\geq t$ all graphs v $\Omega(t)$, $k$ fixed
[MNŠW17] cycles of length $\geq t$ all graphs v $\geq(k-1)t$
[MNŠW17] cycles of length $\geq t$ all graphs v $\geq \frac{(k-1)\log k}{8}$
[BHJ16] cycles of length $\geq t$ all graphs e $O(k \log k + kt)$
[Sim67] all graphs v $>(1+o(1))k \log k$

### Lower bounds for minors

Notice that if $H$ is a subcubic graph, then any negative result about the Erdős-Pósa property of $\mathcal{T}(H)$ implies the same for $\mathcal{M}(H)$. Therefore the table below should be completed with the negative results for subcubic $H$’s that are presented in the following section, in particular those of [BHJ18b].

Ref. Guest class Host class T. Gap at least
$\mathcal{M}(H)$, for every $H$ that has a cycle all graphs v/e $\Omega(k \log k)$
[RS86] $\mathcal{M}(H)$, for every non-planar $H$ graphs of same Euler genus as $H$ v arbitrary
[RT17] $\mathcal{M}(H)$, for every non-planar $H$ graphs of same Euler genus as $H$ e arbitrary
[AKKW16] $\vec{\mathcal{M}}(H)$, for every $H$ that is not butterfly-minor of the cylindrical grid all digraphs v arbitrary
[BJS18] $\mathcal{M}(H)$, for some labelled $H$ that is not 2-connected all graphs v arbitrary
[KM19] graphs of $\mathcal{M}(H)$ meeting $\geq \ell$ of the prescribed subsets, for $\ell \in \mathbb{N}_{\geq 1}$ and $H$ a connected planar graph with $\leq \ell-2$ connected components () square grids with prescribed subsets v arbitrary

### Lower bounds for topological minors

Ref. Guest class Host class T. Gap at least
[Tho88] $\mathcal{T}(H)$, for every planar $H$ that has no plane embedding with all degree-$(\geq 4)$ vertices on the same face all graphs v arbitrary
[RT17] $\mathcal{T}(H)$, for every $H$ non-planar graphs of same Euler genus as $H$ v arbitrary
[Tho88] $\mathcal{T}(H)$, for infinitely many trees $H$ with $\Delta(H)=4$ planar graphs e arbitrary
[RT17] $\mathcal{T}(H)$, for every $H$ subcubic and non-planar graphs of same Euler genus as $H$ e arbitrary
[BHJ18b] $\mathcal{T}(\mathrm{Grid}_{2\times k})$, for every $k\geq 71$ a class of graphs of treewidth $\leq 8$ e arbitrary
[BHJ18b] $\mathcal{T}(H)$, for every subcubic tree $H$ of pathwidth $\geq 19$ a class of graphs of treewidth $\leq 6$ e arbitrary
[AKKW16] $\vec{\mathcal{T}}(H)$, for every $H$ that is not subdivision of the cylindrical wall all digraphs v arbitrary

### Lower bounds for immersions

Ref. Guest class Host class T. Gap at least
copying [Tho88] $\mathcal{I}(H)$, for infinitely many trees $H$ with $\Delta(H)=4$ planar graphs e arbitrary
[Liu15] $\mathcal{I}(H)$ 3-edge-connected graphs e arbitrary
[RT17] $\mathcal{I}(H)$, for every $H$ non-planar graphs of same Euler genus as $H$ v arbitrary
[RT17] $\mathcal{I}(H)$, for every $H$ subcubic and non-planar graphs of same Euler genus as $H$ e arbitrary
[GKRT17] $\mathcal{I}(H)$, for some 3-connected $H$ with $\Delta(H)=4$ planar graphs e arbitrary
[KK18a] $\mathcal{I}(K_5)$ 3-edge-connected graphs e arbitrary

### Lower bounds for induced patterns

Ref. Guest class Host class T. Gap at least
[KK18b] cycles of length $\geq t$, for every $t \geq 5$ all graphs v arbitrary
[KR18] $\mathcal{T}(K_{n,m})$, for every $n\geq 2$ and $m \geq 3$ all graphs v arbitrary
[KR18] $\mathcal{T}(F)$, for every $F$ forest where two $(\geq 3)$-degree vertices lie in the same component all graphs v arbitrary
[KR18] $\mathcal{T}(H)$, for every $H$ that has an induced cycle of length $\geq 5$ all graphs v arbitrary

## References

Last updated: July 2022.