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, a broken link, or an outdated reference, please contact me and I will update the list.

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

Quick links

• positive results: acyclic patterns, triangles, cycles, cycles with length constraints, cycles with prescribed vertices, minors, topological minors, immersions, induced patterns, patterns with prescribed positions, classes with bounded parameters, fractional packings;
• negative results: paths, cycles, minors, topological minors, immersions, induced patterns.

Basic definitions

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

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

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

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

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

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

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

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

Positive results

Acyclic patterns

Ref.	Guest class	Host class	T.	Gap at most	Remarks
[Kőn31]	$K_2$	bipartite	v	$k$
[LY78]	directed cuts	any digraph	e	$k$
[Lov76]	directed cuts	any digraph	e	$k$
[Men27]	$(S,T)$-paths	any	v/e	$k$
[MNL84]	$(S,T)$-paths of length $\geq t$	any	v	$(3(t + 2) - 5)k$
[HU19]	$(S,T)$-paths of length $\geq t$	any	e	unspecified
[Grü38]	directed $(S,T)$-paths	any digraph	v/e	$k$
[Gal64]	$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$
[KKKX20]	directed odd $S$-paths$S\subseteq V(G)$ and a directed odd $S$-path is a directed path of odd length with both endpoints in $S$	any	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	unspecified	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
[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 t$	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$
[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
[Ulm20]	$S$-paths of length $0 \mod m$, where $m$ is an odd prime	any	v	unspecified
[Ulm20]	$S$-paths of length $d \mod m$ if $\forall x,y \in \{0, \dots, m-1\}, y \neq 0 \Rightarrow \exists n \in \mathbb{Z}, 2x+ny = d \mod m$	any	v	unspecified
[CGG+06]	non-zeroAn undirected path in a digraph is non-zero if the sum of the labels of its arcs (with signs depending on the orientation of the edge) is non-zero. $S$-paths	edge-group-labeled digraphs	v	$2k$
[Wol10]	non-zeroA path is non-zero if the sum of the labels of its edges is non-zero. $S$-paths	edge-group-labeled graphs	v	$50 k^4$
[Ulm20]	zero $S$-paths	graphs whose edges are labeled by a finite abelian group	v	unspecified
[Ulm20]	$S$-paths of length $\geq t$ and value $\gamma$, where $\gamma \in \Gamma$	graphs whose edges are labeled by an abelian group $\Gamma$ such that $\forall x,y \in \Gamma, y \neq 0 \Rightarrow \exists n \in \mathbb{Z}, 2x + ny = \gamma$	v	unspecified
[IS17]	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)$
[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$
[SU20]	$S$-$t$-trees$A$ is a vertex set, $t\in \mathbb{N}$ and a $S$-$t$-tree is a tree that contain $m$ vertices of $A$.	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	$\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$
[BFG21]	triangles	graphs $G$ with treewidth $\leq 6$	e	$2k$
[BFG21]	triangles	planar triangulations except $K_4$	e	$1.5k$
[BFG21]	triangles	maximal graphs of treewidth 3	e	$\frac{9}{5}k + \frac{1}{5}$
[BBG+22]	triangles	threshold graphs	e	$2k$
[BBG+22]	triangles	even-balanced co-chain graphs	e	$2k$
[Tuz94]	directed triangles	planar oriented graphs	e	$k$
[MPT18]	directed triangles	directed graphs	e	$2k-1$

Cycles

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

Ref.	Guest class	Host class	T.	Gap at most	Remarks
[Lov65]	cycles	graphs without 2 vertex-disjoint cycles	v	=3
[Vos69]	cycles	graphs without 3 vertex-disjoint cycles	v	=6
[Vos67]	cycles	graphs without 4 vertex-disjoint cycles	v	12	see [Vos69]
[EP65]	cycles	any	v	$O(k\log k)$
[Sim67]	cycles	any	v	$\left (4 + o(1)\right )k \log k$
[Vos69]	cycles	any	v	$\left (2 + o(1) \right )k \log k$
[Vos69]	cycles	any	v	$4k \left (1+ \log \left (k + \frac{3}{2} \right ) \right)$
see [Die05]	cycles	any	e	$(2 + o(1))k \log k$
[DZ02]	cycles	weighted graphs with no induced subdivision of $K_{2,3}$, a wheel, or an 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$
[CHC12] [MYZ13][CGH14]	cycles	planar graphs	v	$3k$
[CGH14]	cycles	graphs that embed in a closed surface of Euler characteristic $\geq 0$	v	$3k$
[CGH14]	cycles	graphs that embed in a closed surface of Euler characteristic $c \leq 0$	v	$3k - 103c$
[KLL02]	cycles	outerplanar graphs	v	$2k$
[Mun16]	cycles	$(K_4, \text{claw}, \text{diamond})$-free graphs	v	$2k$
[Mun16]	cycles	planar claw-free graphs with $\Delta\leq 4$	v	$2k$
[BDM+19]	cycles	planar subcubic graphs	v	$2k$
[MYZ13]	cycles	planar graphs	e	$4k-1$
[BD92]	faces	plane graphs	v	$27k$
[BD92] + [MYZ13]	faces	plane graphs	v	$6k$
[BD92] + [MYZ13] + [GR09]	cycles or facesWhen one is looking for connected covers in planar graphs, covering faces is equivalent to covering cycles (see Lemma 1 in [GR09]).	connected planar graphs with $\delta \geq 3$	v	$66k - 14$	the cover additionally induces a connected subgraph
[RRST96]	directed cycles	any digraph	v	unspecified
[MMP+19]	directed cycles	any digraph	v1/4	$O(k^4)$
[MMP+19]	directed cycles	any digraph	v1/2	$O(k^6)$
[RS96]	directed cycles	planar digraphs	v	$O(k\log(k)\log\log k)$
[RS96] + [GW96]	directed cycles	planar digraphs	v	$63k$
[STV22]	directed cycles	planar digraphs	v	$12k$
[GT11]	directed cycles	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	v1/2	unspecified
[STV22]	any collection of uncrossable cycles	planar graphs or planar digraphs	v	$12k$
[STV22]	any collection of uncrossable cycles	planar graphs or planar digraphs	e	$9.6k$

Cycles with length constraints

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

Ref.	Guest class	Host class	T.	Gap at most	Remarks
[Ree99]	odd cycles	planar graphs	v	superexponential
[FHRV06]	odd cycles	planar graphs	v	$10k$
[KSS12]	odd cycles	planar graphs	v	$\max(0, 6k-2)$
[Tho01]	odd cycles	$2^{3^{9k}}$-connected graphs	v	$2k$
[RR01]	odd cycles	$576k$-connected graphs	v	$2k$
[KR09]	odd cycles	$24k$-connected graphs	v	$2k$
[Ree99]	odd cycles	$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	v1/2	unspecified
[BHJ18a]	even cycles	any	e	$O(k^2 \log k)$The function obtained in [BHJ18a] is $k \mapsto 6kh(k)$, where $h$ is the function for the vertex Erdős-Pósa property of even cycles. It was later proved that $h(k) = O(k \log k)$ (see below, stated for cycles of length $0 \mod t$).
[CJU19]	even cycles	any	e	$O(k \log k)$
[Tho88]	cycles of length $0 \mod t$	any	v	$2^{t^{O(k)}}$
[CC13]	cycles of length $0 \mod t$	any	v	$k~ \mathrm{polylog}~k \cdot 2^{\mathrm{poly}(t)}$
[CHJR18]	cycles of length $0 \mod t$	any	v	$O_t(k \log k)$
[CHJR18]	cycles of length $0 \mod t$	any proper minor-closed class $\mathcal{F}$	v	$O_{t,\mathcal{F}}(k)$
[KW06]	non-zero cycles	$(15k/2)$-connected group-labeled graphs	v	$2k$
[Wol11]	non-zero cycles	group-labeled graphs, c.f. [Wol11]	v	$c^{k^{c’}}$ for some $c,c’$
[Wol11]	cycles of non-zero length mod $2t+1$	any	v	$c^{k^{c’}}$ for some $c,c’$
[HJW18]	doubly non-zero cycles, c.f. [HJW18]	doubly group-labeled graphs	v1/2	unspecified
[HJW18]	odd cycles non homologous to zero	embedded graphs	v1/2	unspecified
[GHK+21]	cycles belonging to certain $\mathbb{Z}_2$-homotopy classes of $\Sigma$	graphs embedded on a surface $\Sigma$	v1/2	unspecified
[GHK+21]	cycles whose valueThe value of a cycle (with respect to an edge-labeling with the elements of some group) is the sum of the labels of its edges. equals a certain value	graphs whose edges are labeled by a finite abelian group	v1/2	unspecified
[GHK+21]	cycles whose valuesThe value of a cycle (with respect to an edge-labeling with the elements of some group) is the sum of the labels of its edges. avoid a finite number of valuesFor each of the groups used in the labeling, a finite number of values to avoid is fixed at the beginning.	graphs whose edges are labeled with finitely many abelian groups	v1/2	unspecified	besides $k$, the gap only depends on the number of groups and of values to avoid
[GHK+21]	cycles whose valuesThe value of a cycle (with respect to a vertex-labeling with the elements of some group) is the sum of the labels of its vertices. avoid a finite number of valuesFor each of the groups used in the labeling, a finite number of values to avoid is fixed at the beginning.	graphs whose vertices are labeled with finitely many abelian groups	v1/2	unspecified	besides $k$, the gap only depends on the number of groups and of values to avoid
[Bir03]	cycles of length $\geq 4$	graphs without 2 vertex-disjoint cycles of length $\geq 4$	v	=4
[Bir03]	cycles of length $\geq 5$	graphs without 2 vertex-disjoint cycles of length $\geq 5$	v	=5
[BBR07]	cycles of length $\geq t$	any	v	$(13+o_t(1))tk^2$
[FH14]	cycles of length $\geq t$	any	v	$(6t+4+o_t(1))k\log k$
[MNŠW17]	cycles of length $\geq t$	any	v	$6kt + (10 + o(1)) k \log k$
[BHJ16]	cycles of length $\geq t$	any	e	$O(k^2 \log k + kt)$
[CJU19]	cycles of length $\geq t$	any	e	$8k(t−1)(\log_2(kt) + 1)$
[KKKX20]	directed odd cycles	any digraph	v1/2	unspecified
[HM13]	directed cycles of length $\geq 3$	any digraph	v	unspecified
[AKKW16]	directed cycles of length $\geq t$	any digraph	v	unspecified

Cycles with prescribed vertices or edges

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

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

Minors

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

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

Ref.	Guest class	Host class	T.	Gap at most
[Sim67]	$\mathcal{M}($complement of ($K_{3,3}$ minus an edge))	any	v	$(4000+o(1))k \log k$
[RS86]	$\mathcal{M}(H)$, $H$ planar	any	v	unspecified
[RS86]	$\mathcal{M}(H)$, $H$ planar with $q$ connected components	${G, \mathbf{tw}(G)\leq t}$	v	$(t-1)(kq-1)$
[FST11]	$\mathcal{M}(H)$, $H$ planar connected	any proper minor-closed class $\mathcal{F}$	v	$O_{H,\mathcal{F}}(k)$
[DKW12]	$\mathcal{M}(K_t)$	$O(kt)$-connected graphs	v	unspecified
[FLM+13]	$\mathcal{M}(\theta_t)$	any	v	$O(t^2k^2)$
[RT13]	$\mathcal{M}(H), \mathbf{pw}(H) \leq 2$ and $H$ connected on $h$ vertices	any	v	$2^{O(h^2)}\cdot k^2\log k$
[CC13] + [CC14]	$\mathcal{M}(H)$, $H$ planar connected on $h$ vertices	any	v	$\mathrm{poly}(h)\cdot k\cdot \mathrm{polylog}~k$
[RST16]	$\mathcal{M}(\theta_t)$	any	e	$k^2t^2 \mathrm{polylog}~kt$
[RST16]	$\mathcal{M}(\theta_t)$	any	e	$k^4t^2 \mathrm{polylog}~kt$
[SU20]	$\mathcal{M}(H)$ where $H$ is the $2 \times 3$ grid	any	e	$O(k^3 \log k)$
[SU20]	$\mathcal{M}(\text{house graph})$	any	e	$O(k^2 \log k)$
[AKKW16]	$\vec{\mathcal{M}}_{b}(H)$, $H$ is a butterfly minor of a cylindrical directed gridIntuitively: concentric cycles directed in the same direction + directed paths between the innermost cycle and the outermost one, in alternating directions. See [AKKW16] for a formal 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 \(\theta_t \cup \theta_{t'}\) by identifying one vertex of \(\theta_t\) with one vertex of \(\theta_{t'}\).	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]	\(\vec{\mathcal{M}}_{s}(H)\)\(\vec{\mathcal{M}}_{s}(H)\) is the class of strong minors of \(H\), i.e. digraphs that can be obtained from \(H\) 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	Remark
[Tho88]	\(\mathcal{T}_{(0 \mod t)}(H)\)\(\mathcal{T}_{(0 \mod t)}(H)\) 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]	\(\mathcal{T}_{(0 \mod t)}(H)\)\(\mathcal{T}_{(0 \mod t)}(H)\) 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]	\(\mathcal{T}_{(0 \mod t)}(H)\)\(\mathcal{T}_{(0 \mod t)}(H)\) 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]	\(\mathcal{T}_{(0 \mod t)}(H)\)\(\mathcal{T}_{(0 \mod t)}(H)\) 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 gridIntuitively: concentric cycles directed in the same direction + directed paths between the innermost cycle and the outermost one, in alternating directions. See [AKKW16] for a formal definition.	any digraph	v	unspecified
[Liu17]	$\mathcal{T}(H)$	any	v1/2	unspecified	holds for rooted subdivisions
[Ray18]	$\vec{\mathcal{T}}(H)$, $H$ strongly-connected	tournaments	v	unspecified
[BP21]	$\vec{\mathcal{T}}(H)$	tournaments	v	$O_H(k \log k)$

Immersions

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

Ref.	Guest class	Host class	T.	Gap at most
[Liu15]	$\mathcal{I}(H)$	4-edge-connected	e	unspecified
[Liu15]	\(\mathcal{I}_{1/2}(H)\)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 \(\mathcal{I}_{1/2}(H)\) denotes the class of all graphs containing $H$ as a half-integral immersion.	any	e1/2	unspecified
[GKRT17]	$\mathcal{I}(H)$, $H$ planar subcubic connected on $h>0$ edges	any	e	$\mathrm{poly}(h \cdot k)$
[GKRT17]	$\mathcal{I}(H)$, $H$ connected on $h>0$ edges	${G, \mathbf{tcw}(G) \leq t}$	e	$h \cdot t^2 \cdot k$
[GKRT17]	$\mathcal{I}(H)$, $H$ connected on $h>0$ edges	${G, \mathbf{tpw}(G) \leq t}$	e	$h \cdot t^2 \cdot k$
[KK18a]	$\mathcal{I}(H)$	4-edge-connected	e	unspecified
[Ray18]	$\vec{\mathcal{I}}(H)$, $H$ strongly-connected	tournaments	e	unspecified
[BP21]	$\vec{\mathcal{I}}(H)$	tournaments	e	$O_H(k^3)$

Induced patterns

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

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

Patterns with prescribed positions

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

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

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

Classes with bounded parameters

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

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

Fractional packings

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

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

Negative results

Lower bounds for paths

Ref.	Guest class	Host class	T.	Gap at least
[MW15]	$H$-valid paths, $H$ with no matching of size $t$	all graphs	v	unavoidable dependency in $t$
[BHJ18a]	$S$-paths of length $p \mod t$, for $t>4$ composite and fixed $p \in \{0, \dots, t-1\}$	all graphs	v/e	arbitrary
[BU18]	$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

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

• [AFH+17] Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond, and Ignasi Sau. A tight Erdős-Pósa function for wheel minors, SIAM Journal on Discrete Mathematics, 32(3):2302-2312, 2018.
• [AKKW16] Saeed Akhoondian Amiri, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Paul Wollan. The Erdős–Pósa property for directed graphs. ArXiv preprint arXiv:0904.0727, 2016.
• [ALBT11] S. Aparna Lakshmanan, Csilla Bujtás, and Zsolt Tuza. Small edge sets meeting all triangles of a graph. Graphs and Combinatorics, 28(3):381–392, 2011.
• [ALM+18] Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Erdős-Pósa Property of Obstructions to Interval Graphs. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, vol. 96, 7:1–7:15, 2018.
• [Alo98] Noga Alon. Piercing $d$-intervals. Discrete & Computational Geometry, 19(3):333–334, 1998.
• [Alo02] Noga Alon. Covering a hypergraph of subgraphs. Discrete Mathematics, 257(2–3):249 – 254, 2002.
• [BBG+22] Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik, Meike Hatzel, Tomáš Masařík, Jana Novotná, and Karolina Okrasa. Tuza’s Conjecture for Threshold Graphs. Discrete Mathematics & Theoretical Computer Science, 14(1), 2022.
• [BBR07] Etienne Birmelé, J. Adrian Bondy, and Bruce A. Reed. The Erdős-Pósa property for long circuits. Combinatorica, 27(2):135–145, 2007.
• [BD92] Daniel Bienstock and Nathaniel Dean. On obstructions to small face covers in planar graphs. Journal of Combinatorial Theory, Series B, 55(2):163–189, 1992.
• [BDM+19] Marthe Bonamy, François Dross, Tomáš Masařík, Wojciech Nadara, Marcin Pilipczuk, and Michał Pilipczuk. Jones’ Conjecture in subcubic graphs. ArXiv preprint arXiv:1912.01570, 2019.
• [BGF21] Fábio Botler, Cristina G. Fernandes, and Juan Gutiérrez. On Tuza’s conjecture for triangulations and graphs with small treewidth. Discrete Mathematics, 344(4):112281, 2021.
• [BH17] Henning Bruhn and Matthias Heinlein. $K_4$-expansions have the edge-Erdős-Pósa property. In Proceedings of EuroComb 2017, Electronic Notes in Discrete Mathematics, 61:163–168, 2017.
• [BHJ16] Henning Bruhn, Matthias Heinlein, and Felix Joos. Long cycles have the edge-Erdős-Pósa property. Combinatorica, 2016.
• [BHJ18a] Henning Bruhn, Matthias Heinlein, and Felix Joos. Frames, A-paths and the Erdős-Pósa property. SIAM Journal on Discrete Mathematics, 32(2):1246–1260, 2018.
• [BHJ18b] Henning Bruhn, Matthias Heinlein, and Felix Joos. The edge-Erdős-Pósa property. Combinatorica, 41(2):147–173, 2021.
• [Bir03] Étienne Birmelé. Largeur d’arborescence, quasi-clique-mineurs et propriétés d’Erdős-Pósa. PhD Thesis. Université Lyon 1, 2003.
• [BJS17] Henning Bruhn, Felix Joos, and Oliver Schaudt. Long cycles through prescribed vertices have the Erdős-Pósa property. Journal of Graph Theory, 87:275–284, 2017.
• [BJS18] Henning Bruhn, Felix Joos, and Oliver Schaudt. Erdős-Pósa property for labelled minors: 2-connected minors. SIAM Journal on Discrete Mathematics, 35(2):893-914, 2021.
• [BP21] Łukasz Bożyk and Michał Pilipczuk. On the Erdős-Pósa property for immersions and topological minors in tournaments. Discrete Mathematics and Theoretical Computer Science, 24(1), 2022.
• [BR00] Claude Berge and Bruce Reed. Optimal packings of edge-disjoint odd cycles. Discrete Mathematics, 211(1–3):197 – 202, 2000.
• [Bru19] Henning Bruhn. Even A-cycles have the edge-Erdős-Pósa property. Journal of Graph Theory, 100(2):281-293, 2022.
• [BT15] Nicolas Bousquet and Stéphan Thomassé. VC-dimension and Erdős–Pósa property. Discrete Mathematics, 338(12):2302 – 2317, 2015.
• [BU18] Henning Bruhn and Arthur Ulmer. Packing A-paths of length zero modulo four. European Journal of Combinatorics, 99:103422, 2022.
• [CC13] Chandra Chekuri and Julia Chuzhoy. Large-treewidth graph decompositions and applications. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 291–300. ACM, 2013.
• [CC14] Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 60–69. ACM, 2014.
• [CGG+06] Maria Chudnovsky, Jim Geelen, Bert Gerards, Luis Goddyn, Michael Lohman, and Paul Seymour. Packing non-zero $A$-paths in group-labelled graphs. Combinatorica, 26(5):521–532, 2006.
• [CGH14] Glenn G. Chappell, John Gimbel, and Chris Hartmann. On cycle packings and feedback vertex sets. Contributions to Discrete Mathematics, 9(2), 2014.
• [CHC12] Hong-Bin Chen, Fu Hung-Lin, and Shih Chie-Huai. Feedback vertex set on planar graphs. Taiwanese Journal of Mathematics, 16.6:2077-2082,2012.
• [CHJR18] Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, and Jean-Florent Raymond. A tight Erdős-Pósa function for planar minors. Advances in Combinatorics, 2019:2, 2019.
• [CJU19] Wouter Cames van Batenburg, Gwenaël Joret, and Arthur Ulmer. Erdős-Pósa from ball packing. SIAM Journal on Discrete Mathematics, 34(3):1609-1619, 2020.
• [CRST17] Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, and Dimitrios M. Thilikos. An $O( \log \rm {OPT})$-approximation for covering/packing minor models of $\theta_r$. Algorithmica, 2018, 80(4):1330–1356.
• [Die05] Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Heidelberg, third edition, 2005.
• [DKW12] Reinhard Diestel, Ken-ichi Kawarabayashi, and Paul Wollan. The Erdős–Pósa property for clique minors in highly connected graphs. Journal of Combinatorial Theory, Series B, 102(2):454–469, 2012.
• [DNL87] IJ Dejter and V Neumann-Lara. Unboundedness for generalized odd cyclic transversality. In Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, volume 52, pages 195–203, 1987.
• [DO96] Guoli Ding and Bogdan Oporowski. On tree-partitions of graphs. Discrete Mathematics, 149(1–3):45 – 58, 1996.
• [DXZ03] Guoli Ding, Zhenzhen Xu, and Wenan Zang. Packing cycles in graphs, II. Journal of Combinatorial Theory, Series B, 87(2):244–253, 2003.
• [DZ02] Guoli Ding and Wenan Zang. Packing cycles in graphs. Journal of Combinatorial Theory, Series B, 86(2):381 – 407, 2002.
• [EP65] Paul Erdős and Louis Pósa. On independent circuits contained in a graph. Canadian Journal of Mathematics, 17:347–352, 1965.
• [FH14] Samuel Fiorini and Audrey Herinckx. A tighter Erdős-Pósa function for long cycles. Journal of Graph Theory, 77(2):111–116, 2014.
• [FHRV06] Samuel Fiorini, Nadia Hardy, Bruce Reed, and Adrian Vetta. Approximate min-max relations for odd cycles in planar graphs. Mathematical Programming, 110(1):71-91. Springer, 2006.
• [FJW13] Samuel Fiorini, Gwenaël Joret, and David R. Wood. Excluded forest minors and the Erdős-Pósa property. Combinatorics, Probability & Computing, 22(5):700–721, 2013.
• [FLM+13] Fedor V Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Quadratic upper bounds on the Erdős–pósa property for a generalization of packing and covering cycles. Journal of Graph Theory, 74(4):417–424, 2013.
• [FS13] Alexandra Fradkin and Paul Seymour. Tournament pathwidth and topological containment. Journal of Combinatorial Theory, Series B, 103(3):374 – 384, 2013.
• [FST11] Fedor V. Fomin, Saket Saurabh, and Dimitrios M. Thilikos. Strengthening Erdős–Pósa property for minor-closed graph classes. Journal of Graph Theory, 66(3):235–240, 2011.
• [Gal64] Tibor Gallai. Maximum-minimum sätze und verallgemeinerte faktoren von graphen. Acta Mathematica Hungarica, 12, 03 1964.
• [GGR+09] Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, and Adrian Vetta. On the odd-minor variant of Hadwiger’s conjecture. Journal of Combinatorial Theory, Series B 99(1):20–29, 2009.
• [GHK+21] Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi, O-joug Kwon, and Sang-il Oum. A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups. arXiv preprint arXiv:2102.01986. January 2021.
• [GKRT17] Archontia Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Packing and covering immersion models of planar subcubic graphs. European Journal of Combinatorics, 65:154–167, 2017.
• [GL69] András Gyárfás and Jenö Lehel. A Helly-type problem in trees. In Combinatorial Theory and its applications, pages 571–584. Colloquia Mathematica Societatis J'anos Bolyai, 1969.
• [GR09] Alexanders Grigoriev and René Sitters. Connected feedback vertex set in planar graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), volume 5911 of LNCS, pages 143–153. Springer, Berlin, Heidelberg, 2009.
• [Grü38] Tibor Grünwald. Ein neuer beweis eines mengerschen satzes. Journal of the London Mathematical Society, 1(3):188–192, 1938.
• [GT11] Bertrand Guenin and Robin Thomas. Packing directed circuits exactly. Combinatorica, 31(4):397–421, 2011.
• [GV95] Yubao Guo and Lutz Volkmann. A generalization of Menger’s theorem for certain block-cactus graphs. Graphs and Combinatorics, 11(1):49–52, 1995.
• [GW96] Michel Goemans and David Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica, 18:37–39, 1998.
• [Hax99] Penny Haxell. Packing and covering triangles in graphs. Discrete Mathematics, 195(1–3):251 – 254, 1999.
• [HJW18] Tony Huynh, Felix Joos, and Paul Wollan. A unified Erdős–Pósa theorem for constrained cycles. Combinatorica, 2018.
• [HK88] Penny Haxell and Y. Kohayakawa. Packing and covering triangles in tripartite graphs. Graphs and Combinatorics, 14(1):1–10, 1988.
• [HKT11] Penny Haxell, Alexandr Kostochka, and Stéphan Thomassé. Packing and covering triangles in $K_4$-free planar graphs. Graphs and Combinatorics, 28(5):653–662, 2011.
• [HM13] Frédéric Havet and Ana Karolinna Maia. On disjoint directed cycles with prescribed minimum lengths. Research Report RR-8286, INRIA, April 2013.
• [HS58] András Hajnal and János Surányi. Über die auflösung von graphen in vollständige teilgraphen. Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica, 1:113–121, 1958.
• [HU19] Matthias Heinlein and Arthur Ulmer. Long $A$-$B$-paths have the edge-Erdős-Pósa property. arXiv preprint arXiv:1903.07989, 2019.
• [IS17] Sharat Ibrahimpur and Chaitanya Swamy. Min-Max Theorems for Packing and Covering Odd $(u,v)$-trails. In Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 279–291, 2017.
• [Joo14] Felix Joos. Parity linkage and the Erdős-Pósa property of odd cycles through prescribed vertices in highly connected graphs. Journal of Graph Theory, to appear in 2017.
• [JRST01] Thor Johnson, Neil Robertson, Paul D. Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138 – 154, 2001.
• [Kai97] Tomás Kaiser. Transversals of $d$-intervals. Discrete & Computational Geometry, 18(2):195–203, 1997.
• [KK12] Naonori Kakimura and Ken-ichi Kawarabayashi. Packing directed circuits through prescribed vertices bounded fractionally. SIAM Journal on Discrete Mathematics, 26(3):1121–1133, 2012.
• [KK13] Naonori Kakimura and Ken-ichi Kawarabayashi. Half-integral packing of odd cycles through prescribed vertices. Combinatorica, 33(5):549–572, 2013.
• [KK15] Naonori Kakimura and Ken-ichi Kawarabayashi. Fixed-parameter tractability for subset feedback set problems with parity constraints. Theoretical Computer Science, 576:61–76, 2015.
• [KK16] Ken-ichi Kawarabayashi and Yusuke Kobayashi. Edge-disjoint odd cycles in 4-edge-connected graphs. Journal of Combinatorial Theory, Series B, 119:12–27, 2016.
• [KK18a] Naonori Kakimura and Ken-ichi Kawarabayashi. The Erdős–Pósa property for edge-disjoint immersions in 4-edge-connected graphs. Journal of Combinatorial Theory, Series B, 131:138–169, 2018.
• [KK18b] Eun Jung Kim and O-joung Kwon. Erdős-Pósa property of chordless cycles and its applications. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.
• [KKKK13] Ken-ichi Kawarabayashi, Daniel Král, Marek Krčál, and Stephan Kreutzer. Packing directed cycles through a specified vertex set. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 365–377. Society for Industrial and Applied Mathematics, 2013.
• [KKKX20] Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, and Qiqin Xie. Half-integral Erdős-Pósa property of directed odd cycles. arXiv preprint arXiv:2007.12257, 2020.
• [KKL19] Minjeong Kang, O-joung Kwon, and Myounghwan Lee. Graphs without two vertex-disjoint S-cycles. Discrete Mathematics, 343(10):111997, 2020.
• [KKM11] Naonori Kakimura, Ken-ichi Kawarabayashi, and Dániel Marx. Packing cycles through prescribed vertices. Journal of Combinatorial Theory, Series B, 101(5):378 – 381, 2011.
• [KLL02] Tom Kloks, Chuan-Min Lee, and Jiping Liu. New algorithms for $k$-face cover, $k$-feedback vertex set, and $k$-disjoint cycles on plane and planar graphs. In 28th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2002), volume 2573 of LNCS, pages 282–295. Springer, Berlin, 2002.
• [KM19] O-joung Kwon and Dániel Marx. Erdős-Pósa property of minor-models with prescribed vertex sets. arXiv preprint arXiv:1904.00879, 2019.
• [KN07] Ken-ichi Kawarabayashi and Atsuhiro Nakamoto. The Erdős–Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces. Discrete Mathematics, 307(6):764 – 768, 2007.
• [Kőn31] Denés Kőnig. Gráfok és mátrixok. Matematikai és Fizikai Lapok, 38:116–119. 1931.
• [KR09] Ken-ichi Kawarabayashi and Bruce Reed. Highly parity linked graphs. Combinatorica, 29(2):215–225, 2009.
• [KR18] O-joung Kwon and Jean-Florent Raymond. Packing and covering induced subdivisions. SIAM Journal on Discrete Mathematics, 35(2):597-636, 2021.
• [Kri95] Michael Krivelevich. On a conjecture of Tuza about packing and covering of triangles. Discrete Mathematics, 142(1–3):281 – 286, 1995.
• [KSS12] Daniel Král’, Jean-Sébastien Sereni, and Ladislav Stacho. Min-Max Relations for Odd Cycles in Planar Graphs. SIAM Journal on Discrete Mathematics, 26(3):884-895, 2012.
• [KV04] Daniel Král’ and Heinz-Jürgen Voss. Edge-disjoint odd cycles in planar graphs. Journal of Combinatorial Theory, Series B, 90(1):107 – 120, 2004.
• [KW06] Ken-ichi Kawarabayashi and Paul Wollan. Non-zero disjoint cycles in highly connected group labelled graphs. Journal of Combinatorial Theory, Series B, 96(2):296–301, 2006.
• [Liu15] Chun-Hung Liu. Packing and Covering Immersions in 4-Edge-Connected Graphs. Journal of Combinatorial Theory, Series B, 151:148–222, 2021.
• [Liu17] Chun-Hung Liu. Packing topological minors half-integrally. ArXiv preprint arXiv:1707.07221, July 2017.
• [Lov65] László Lovász. On graphs not containing independent circuits. (Hungarian) Matematikai Lapok, 16(7):289-299, 1965.
• [Lov76] László Lovász. On two minimax theorems in graph. Journal of Combinatorial Theory, Series B, 21(2):96–103, 1976.
• [LBT16] Aparna Lakshmanan S., Csilla Bujtás, and Zsolt Tuza. Induced cycles in triangle graphs. Discrete Applied Mathematics, 209:264–275, 2016.
• [LY78] Claudio L. Lucchesi and D. H. Younger. A minimax theorem for directed graphs. Journal of the London Mathematical Society (2), 17(3):369–374, 1978.
• [Mad78a] Wolfgang Mader. Über die maximalzahl kantendisjunkter $A$-wege. Archiv der Mathematik, 30(1):325–336, 1978.
• [Mad78b] Wolfgang Mader. Über die maximalzahl kreuzungsfreier $H$-wege. Archiv der Mathematik, 31(1):387–402, 1978.
• [Men27] Karl Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 1(10):96–115, 1927.
• [MMP+19] Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, and Manuel Sorge. Packing directed circuits quarter-integrally. ArXiv preprint arXiv:1907.02494, 2019.
• [MNL85] Luis Montejano and Victor Neumann-Lara. A variation of Menger’s theorem for long paths. Journal of Combinatorial Theory, Series B, 36(2):213–217, 1984.
• [MNŠW17] Franck Mousset, Andreas Noever, Nemanja Škorić, and Felix Weissenberger. A tight Erdős-Pósa function for long cycles. Journal of Combinatorial Theory, Series B, 125:21–32, 2017.
• [MPT18] Jessica McDonald, Gregory J. Puleo, Craig Tennenhouse. Packing and covering directed triangles. Graphs and Combinatorics, 3694):1059–1063, 2020.
• [Mun16] Andrea Munaro. On some classical and new hypergraph invariants. PhD Thesis. Université Grenoble Alpes, 2016.
• [MW15] Dániel Marx and Paul Wollan. An exact characterization of tractable demand patterns for maximum disjoint path problems. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 642–661. SIAM, 2015.
• [MYZ13] Jie Ma, Xingxing Yu, and Wenan Zang. Approximate min-max relations on plane graphs. Journal of Combinatorial Optimization, 26(1):127–134, 2013.
• [Pul15] Gregory J. Puleo. Tuza’s Conjecture for Graphs with Maximum Average Degree less than 7. European Journal of Combinatorics, 49:134–152, 2015.
• [PW12] Matteo Pontecorvi and Paul Wollan. Disjoint cycles intersecting a set of vertices. Journal of Combinatorial Theory, Series B, 102(5):1134 – 1141, 2012.
• [Ray18] Jean-Florent Raymond. Hitting minors, subdivisions, and immersions in tournaments. Discrete Mathematics & Theoretical Computer Science, 20(1):4212, 2018.
• [Ree99] Bruce A. Reed. Mangoes and blueberries. Combinatorica, 19(2):267–296, 1999.
• [RR01] Dieter Rautenbach and Bruce Reed. The Erdős–Pósa property for odd cycles in highly connected graphs. Combinatorica, 21(2):267–278, 2001.
• [RRST96] Bruce Reed, Neil Robertson, Paul Seymour, and Robin Thomas. Packing directed circuits. Combinatorica, 16(4):535–554, 1996.
• [RS86] Neil Robertson and Paul D. Seymour. Graph Minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(2):92–114, 1986.
• [RS96] Bruce A. Reed and Bruce F. Shepherd. The Gallai-Younger conjecture for planar graphs. Combinatorica, 16(4):555–566, 1996.
• [RST16] Jean-Florent. Raymond, Ignasi. Sau, and Dimitrios M. Thilikos. An edge variant of the Erdős-Pósa property. Discrete Mathematics, 339(8):2027 – 2035, 2016.
• [RT13] Jean-Florent Raymond and Dimitrios M. Thilikos. Polynomial gap extensions of the Erdős-Pósa theorem. In Jaroslav Nešetřil and Marco Pellegrini, editors, The Seventh European Conference on Combinatorics, Graph Theory and Applications, volume 16 of CRM Series, pages 13–18. Scuola Normale Superiore, 2013.
• [RT17] Jean-Florent Raymond and Dimitrios M. Thilikos. Recent techniques and results on the Erdős-Pósa property. Discrete Applied Mathematics, 231:25-43, 2017.
• [Sam83] E. Sampathkumar. A generalization of Menger’s theorem for trees. Journal of Combinatorics, Information and System Sciences, 8:78–80, 1983.
• [Sam92] E. Sampathkumar. A generalization of Menger’s theorem for certain unicyclic graphs. Graphs and Combinatorics, 8(4):377–380, 1992.
• [Sch01] Alexander Schrijver. A short proof of Mader’s $S$-paths theorem. Journal of Combinatorial Theory, Series B, 82(2):319–321, 2001.
• [Sey95] Paul D. Seymour. Packing directed circuits fractionally. Combinatorica, 15:281–288, 1995.
• [Sey96] Paul D. Seymour. Packing circuits in Eulerian digraphs. Combinatorica, 16(2):223–231, 1996.
• [Sim67] Miklós Simonovits. A new proof and generalizations of a theorem of Erdős and Pósa on graphs without $k+1$ independent circuits. Acta Mathematica Academiae Scientiarum Hungarica, 18(1):191–206, 1967.
• [SS04] András Sebő and László Szegő. The path-packing structure of graphs. In Daniel Bienstock and George Nemhauser, editors, Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings, pages 256–270, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
• [STV22] Niklas Schlomber, Hanjo Thiele, and Jens Vygen. Packing cycles in planar and bounded-genus graphs. arXiv preprint arXiv:2207.00450, 2022.
• [SU20] Raphael Steck and Arthur Ulmer. Long Ladders do not have the edge-Erdős-Pósa property. arXiv preprint arXiv:2003.03236, 2020.
• [Tho88] Carsten Thomassen. On the presence of disjoint subgraphs of a specified type. Journal of Graph Theory, 12(1):101–111, 1988.
• [Tho01] Carsten Thomassen. The Erdős-Pósa property for odd cycles in graphs of large connectivity. Combinatorica, 21(2):321–333, 2001.
• [Tuz90] Zsolt Tuza. A conjecture on triangles of graphs. Graphs and Combinatorics, 6(4):373–380, 1990.
• [Tuz94] Zsolt Tuza. Perfect triangle families. Bulletin of the London Mathematical Society, 26:321-324, 1994.
• [TV89] Jerzy Topp and Lutz Volkmann. A generalization of Menger’s theorem for trees. Journal of Combinatorics, Information and System Sciences, 14(4):249–250, 1989.
• [Ulm20] Arthur Ulmer. Zero A-paths and the Erdős-Pósa property. arXiv e-print arXiv:2010.00663. October 2020.
• [Vos67] Heinz-Jürgen Voss. Über die Anzahl von Knotenpunkten, die in einem Graphen, der keine drei unabhangige Kreise enthalt, alle Kreise reprasentieren. Wiss. Z. TH Ilmenau 13 Nr. 4/2, 413-418, 1967. Apparently impossible to find online but cited in [Vos69].
• [Vos68] Heinz-Jürgen Voss. Some properties of graphs containing $k$ independent circuits. Theory of Graphs, Proceedings of the Colloquium held at Tihany, Hungary, September 1966. Akademiai Kiadó. Publishing House of the Hungarian Academy of Sciences, 321-334, 1968.
• [Vos69] Heinz-Jürgen Voss. Eigenschaften von Graphen, die keine $k+1$ knotenfremde Kreise enthalten. Mathematische Nachrichten, 40:19-25, 1969.
• [Wei18] Daniel Weißauer. In absence of long chordless cycles, large tree-width becomes a local phenomenon, Journal of Combinatorial Theory, Series B, 139:342-352, 2019.
• [Wol10] Paul Wollan. Packing non-zero $A$-paths in an undirected model of group labeled graphs. Journal of Combinatorial Theory, Series B, 100(2): 141–150, 2010.
• [Wol11] Paul Wollan. Packing cycles with modularity constraints. Combinatorica, 31(1):95–126, 2011.

Last updated: July 2022.