# 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.

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)$.

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 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.

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
[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$
[Mad78a] any e $2k$ (see [SS04], [BHJ18a])
[HU19] of length $\geq t$ any e unspecified
[CGG+06] non-zero $S$-paths () edge-group-labeled digraphs v $2k$
[Wol10] non-zero $S$-paths () edge-group-labeled graphs v $50 k^4$
[GGR+09] odd any v $2k$
[BHJ18a] of length at least $t$ any v $4kt$
[HU19] of length $\geq \ell$ 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
[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
[Lov65] cycles graphs without 2 vertex-disjoint cycles v =3
[Vos69] cycles graphs without 3 vertex-disjoint cycles v =6
[Vos67] (see [Vos69]) cycles graphs without 4 vertex-disjoint cycles v 12
[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$
[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$
[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$
[KKKX20] directed odd cycles any digraph v1/2 unspecified
[HJW18] cycles non homologous to zero embedded graphs v1/2 unspecified

### Cycles with length constraints

Ref. Guest class Host class T. Gap at most
[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
[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)$
[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

For every $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
[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

### 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
[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
[Ray18] $\vec{\mathcal{T}}(H)$, $H$ strongly-connected tournaments v unspecified

### 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

### 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}$-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 $k$ $\tau$ Relationship
[Sey95] directed cycles any digraph max fractional vertex packing min integral vertex covering $\tau \leq 4k \ln(4k) \ln\log(4k)$

## 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
[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] (see [Vos69]) cycles graphs without 4 vertex-disjoint cycles v \geq 9
[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] (see [Vos68]) cycles all graphs v $\geq \frac{1}{8} k \log k$
[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$
directed cycles planar digraphs v $3/2$
[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

Last updated: August 2020.