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

Quick links:

### 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}$. A $\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}$.

We say that a class $\mathcal{H}$ (refered to as 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}$, if $G$ has no $\mathcal{H}$-vertex-packing in $G$ of size $k+1$, then $G$ has a $\mathcal{H}$-vertex-covering of size $f(k)$. Notice that a slightly 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 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 of the tables (T.) refers to the type of Erdős–Pósa property: v for vertex, e for edge, w for weighted, v$_{1/2}$ for vertex half-integral, …

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$
[MPT18] directed triangles directed graphs e $2k-1$

### Cycles

For cycles with length or modularity constraints, see the next table.

Ref. Guest class Host class T. Gap at most
[EP65] cycles any v $O(k\log k)$
[Sim67] cycles any v $\left (4 + o(1)\right )k \log k$
[Vos68] cycles any v $\left (2 + o(1) \right )k \log k$
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$
[MYZ13] cycles planar graphs v $3k$
[BD92] facial cycles plane graphs v $27k$
[BD92] + [MYZ13] facial cycles plane graphs v $6k$
[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$
[MYZ13] cycles planar graphs e $4k-1$
[RRST96] directed cycles any digraph v unspecified
[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 $\text{v}_{1/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 $\text{v}_{1/2}$ unspecified
[BHJ18a] even cycles any e
[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 $\text{v}_{1/2}$ unspecified
[HJW18] odd cycles non homologous to zero embedded graphs $\text{v}_{1/2}$ unspecified
[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)$
[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)$
[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 $\text{v}_{1/2}$ unspecified
[KK12] directed $S$-cycles all digraphs $\text{v}_{1/5}$ unspecified
[KKKK13] odd directed $S$-cycles any digraph $\text{v}_{1/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 $\mathrm{v}_{1/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 $\text{e}_{1/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$

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

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

 [Tuz90] triangles all graphs e $\geq 2k$ [EP65] cycles all graphs v $\Omega(k \log k)$ [Sim67] cycles all graphs v $> \left (\frac{1}{2} + o(1) \right ) k \log k$ [Vos68] cycles all graphs v $\geq \left (\frac{1}{8} + o(1) \right )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 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-2$ [KV04] odd cycles planar graphs e $\geq 2k$ [PW12] $S$-cycles all graphs v $\Omega(k\log k)$ [KK13] odd $S$-cycles all graphs v arbitrary [KK12] directed $S$-cycles all diraphs v/e arbitrary [KKKK13] odd directed $S$-cycles all digraphs v arbitrary [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] dumb-bellsA dumb-bell is a graph obtained by connecting two cycles by a (non-trivial) path. 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: May 2019.