Jean-Florent Raymond

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] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ any v $2k$
[GV95] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$, $S$ independent graphs where every block has $\leq 2$ cutvertices and is either a cycle or a clique v $k$
[Sam92] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$, $S$ independent unicyclic graphs whose cycle has $\leq 2$ vertices of degree $\geq 3$ v $k$
[Sam83] [TV89] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$, $S$ independent trees v $k$
[Mad78b] $\mathcal{S}$-paths$\mathcal{S}$ is a collection of disjoint subsets of $V(G)$ and a $\mathcal{S}$-path is a path connecting different sets in $\mathcal{S}$ any v see [Sch01]
[Mad78a] $\mathcal{S}$-paths$\mathcal{S}$ is a collection of disjoint subsets of $V(G)$ and a $\mathcal{S}$-path is a path connecting different sets in $\mathcal{S}$ any e $2k$ (see [SS04], [BHJ18a])
[HU19] $\mathcal{S}$-paths$\mathcal{S}$ is a collection of disjoint subsets of $V(G)$ and a $\mathcal{S}$-path is a path connecting different sets in $\mathcal{S}$ of length $\geq t$ any e unspecified
[CGG+06] non-zero $S$-paths (directed modelAn undirected path is non-zero if the sum of the labels of its edges (with signs depending on the orientation of the edge) is non-zero.) edge-group-labeled digraphs v $2k$
[Wol10] non-zero $S$-paths (undirected modelA path is non-zero if the sum of the labels of its edges is non-zero.) edge-group-labeled graphs v $50 k^4$
[GGR+09] odd $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ any v $2k$
[BHJ18a] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length at least $t$ any v $4kt$
[HU19] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length $\geq \ell$ any e unspecified
[BHJ18a] even $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ any v $10k$
[BHJ18a] $S$-$t$-combsAn elementary $t$-comb can be obtained by adding a pendant vertex to each internal vertex of a path on $t$ edges. A $t$-comb is any subdivision of an elementary $t$-comb. Let $S\subseteq V(G)$. A $S$-$t$-comb is a $t$-comb whose leaves, and only the leaves, belong to $S$. any v $4kt$
[BU18] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length $0 \mod 4$ any v unspecified
[BU18] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length $2 \mod 4$ any v unspecified
[IS17] odd $(u,v)$-trailsAn $(u,v)$-trail is a walk from $u$ to $v$ that may have repeated vertices but no repeated edge. A trail is odd if it has an odd number of edges. 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 $\mathcal{T}(K_{3,3})$$\mathcal{T}(H)$ is the class of graphs containing a subdivision of $H$-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 flatA graph is flat if every edge belongs to at most two triangles. graphs e $3k/2$
[Pul15] triangles graphs with $\mathrm{mad} < 7$ e $2k$
[LBT16] triangles graphs whose triangle graphThe triangle graph of $G$ is the graph whose vertices are triangles of $G$ and where two edges are adjacent if the corresponding triangles share an edge. 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 odd ringAn odd ring is a graph obtained from an odd cycle by replacing every edge ${u,v}$ by either a triangle containing ${u,v}$, or by two triangles on vertices ${u,a,b}$ and ${v,c,d}$ together with the edges ${b,c}$ and ${a,d}.$ w $k$
[DXZ03] cycles graphs with no induced subdivision of $K_{3,3}$, a wheel, or an odd ringAn odd ring is a graph obtained from an odd cycle by replacing every edge ${u,v}$ by either a triangle containing ${u,v}$, or by two triangles on vertices ${u,a,b}$ and ${v,c,d}$ together with the edges ${b,c}$ and ${a,d}.$ 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 strongly planar digraphsA digraph is strongly planar if it has a planar drawing such that for every vertex $v$, the edges with head $v$ form an interval in the cyclic ordering of edges incident with $v$ (definition from [GT11]). v $k$
[GT11] directed cycles digraphs with no butterfly minorSee [GT11] for a definition. isomorphic to an odd double circuitAn odd double circuit is a digraph obtained from an undirected circuit of odd length more than 2 by replacing each edge by a pair of directed edges, one in each direction. or $F_7$$F_7$ is the digraph obtained from the directed cycle on vertices $v_1, \dots, v_7,v_1$, by adding the edges creating the directed cycle $v_1,v_3, v_5, v_7, v_2, v_4, v_6, v_1$. 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 $k$-near bipartiteA graph is $k$-near bipartite if every set of $p$ vertices contains a stable set of size at least $p/2 - k$. 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 $O(k^2 \log k)$The function obtained in [BHJ18a] is $k \mapsto 6kf(k)$, where $f$ is the function for the vertex Erdős-Pósa property of even cycles. It was later proved that $f(k) = O(k \log k)$ (see below, stated for cycles of length $0 \mod t$).
[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] $(S,S’)$-cycles$S,S’ \subseteq V(G)$ and an $(S,S’)$-cycle is a cycle that contains vertices of both $S$ and $S’$ 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 cylindrical directed gridSee [AKKW16] for a definition. 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] $\mathcal{M}(\theta_{t,t’})$$\theta_{t,t’}$ is the multigraph obtained from by identifying one vertex of with one vertex of . simple graphs e unspecified
[BH17] $\mathcal{M}(K_4)$ any e $O(k^8 \log k)$
[AFH+17] $\mathcal{M}(W_t)$$W_t$ is the wheel on $t+1$ vertices, i.e. the graph obtained by adding a dominating vertex to a cycle of length $t$., $t \in \mathbb{N}$ any v $O_t(k \log k)$
[Ray18] is the class of strong minors of , i.e. digraphs that can be obtained from after contracting strongly-connected subgraphs. 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 proper subclassSee the paper for the details and the definition of minors in labeled graphs. 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 (detailsThe host graph $G$ comes with a number of prescribed vertex subsets and the guest graphs are those subgraphs of $G$ that can be constracted to $H$ and intersect $\geq \ell$ of the prescribed subsets. The gap function does not depend on the number of prescribed subsets of the host graph.) 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] is the class of subdivisions of $H$ where every edge is subdivided into a path on $0 \mod t$ edges., $H$ connected planar subcubic any v unspecified
from [CC13] is the class of subdivisions of $H$ where every edge is subdivided into a path on $0 \mod t$ edges., $H$ connected planar subcubic any v $O_{H,t}(k~ \mathrm{polylog}~k)$
[CHJR18] is the class of subdivisions of $H$ where every edge is subdivided into a path on $0 \mod t$ edges., $H$ planar subcubic any v $O_{H,t}(k \log k)$
[CHJR18] is the class of subdivisions of $H$ where every edge is subdivided into a path on $0 \mod t$ edges., $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 cylindrical directed gridSee [AKKW16] for a definition. any digraph v unspecified
[Liu17] $\mathcal{T}(H)$ (note)The main result of [Liu17] is in fact stronger as is works for rooted subdivisions. See the paper for details. 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] A graph $H$ is a half-integral immersion of a graph $G$ is $H$ is an immersion of the graph obtained by $G$ after duplicating the multiplicity of all its edges and denotes the class of all graphs containing $H$ as a half-integral immersion. 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] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length $1 \mod 4$ all graphs v arbitrary
[BU18] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length $3 \mod 4$ all graphs v arbitrary
[BHJ18a] odd/even $S$-$T$-paths$S,T\subseteq V(G)$ and a $S$-$T$-path is a path with an endpoint in $S$ and the other one in $T$. all graphs v/e arbitrary
[BHJ18a] odd/even $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ all graphs e arbitrary
[BHJ18a] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length $0 \mod 4$ all graphs e arbitrary
[BHJ18a] $S$-paths$S\subseteq V(G)$ and a $S$-path is a path with both endpoints in $S$ of length $0 \mod p$, for any prime $p$ all graphs e arbitrary
[IS17] odd $(u,v)$-trailsAn $(u,v)$-trail is a walk from $u$ to $v$ that may have repeated vertices but no repeated edge. A trail is odd if it has an odd number of edges. all graphs e $\geq 2k+1$
[BHJ18a] $S$-$T$-$S$-paths$S.T \subseteq V(G)$. A $S$-$T$-$S$-path is a $S$-path that contains vertices of $T$. all graphs e arbitrary
[BHJ18a] directed $S$-$T$-$S$-paths$S.T \subseteq V(G)$. A directed $S$-$T$-$S$-path is a directed $S$-path that contains vertices of $T$. all digraphs v/e arbitrary
[BHJ18a] odd/even directed $S$-paths$S\subseteq V(G)$ and a directed $S$-path is a directed path with both endpoints in $S$. 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
[?]This follows from the existence of $n$-vertex 3-regular graphs with treewidth $\Omega(n)$ and girth $\Omega(\log n)$ (Ramanujan graphs, for instance). $\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 (and other cases)See the paper for the details and the definition of minors in labelled graphs. 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 (detailsThe host graph $G$ comes with a number of prescribed vertex subsets and the guest graphs are those subgraphs of $G$ that can be constracted to $H$ and intersect $\geq \ell$ of the prescribed subsets.) 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)$ for some $H$Actually this is not proved in the preprint [Liu15] but stated as a consequence of a manuscript of the author that is not availlable online. A description of the graphs $H$ such that $\mathcal{I}(H)$ does not have the edge-EP property in 3-edge-connected graphs is not given in [Liu15]. 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: May 2019.