Dynamic Erdős-Pósa listing

This page is an attempt to construct an exhaustive listing of results about the Erdős–Pósa property for graphs. Some data has been collected when preparing this article.
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 or a broken link, 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)$.

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$
[Mad78b] any v see [Sch01]
[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$
[BHJ18a] any v $4kt$
[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)$

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)$
[RS96] directed cycles planar digraphs v $O(k\log(k)\log\log k)$
[RS96] + [GW96] directed cycles planar digraphs v $O(k)$
[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

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

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
[KK12] directed $S$-cycles all diraphs 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: January 2020.