# Dynamic Erdős-Pósa listing

This page is an attempt to construct an exhaustive listing of results about the Erdős–Pósa property for graphs. Some data has been collected when preparing this article.

Note that **the papers listed on this page have not all been peer-reviewed** (yet). All of them are availlable online or have been published in a journal or conference proceedings with peer-review.

If you notice a missing result, a typo or a broken link, please contact me and I will update the list.

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

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

**Notice that a different definition of the gap (with $k+1$ replaced by $k$ above) is sometimes used in the litterature (but not on this page), leading to slightly different values of the gap.**
The notions of *$\mathcal{H}$-edge-packing*, *$\mathcal{H}$-edge-cover*, and *edge-Erdős–Pósa property* can be defined similarly by replacing “vertex” by “edge” in the definitions above.

The fourth column (T.) of the tables below refers to the type of Erdős–Pósa property: *v* for vertex and *e* for edge. The definitions of the other variants of the Erdős–Pósa property mentioned below (*w* for weighted, *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 |
---|---|---|---|---|

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

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

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

[Tuz94] | directed triangles | planar oriented graphs | e | $k$ |

[MPT18] | directed triangles | directed graphs | e | $2k-1$ |

### Cycles

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

Ref. | Guest class | Host class | T. | Gap at most |
---|---|---|---|---|

[Lov65] | cycles | graphs without 2 vertex-disjoint cycles | v | =3 |

[Vos69] | cycles | graphs without 3 vertex-disjoint cycles | v | =6 |

[Vos67] (see [Vos69]) | cycles | graphs without 4 vertex-disjoint cycles | v | 12 |

[EP65] | cycles | any | v | $O(k\log k)$ |

[Sim67] | cycles | any | v | $\left (4 + o(1)\right )k \log k$ |

[Vos69] | cycles | any | v | $\left (2 + o(1) \right )k \log k$ |

[Vos69] | cycles | any | v | $4k \left (1+ \log \left (k + \frac{3}{2} \right ) \right)$ |

see [Die05] | cycles | any | e | $(2 + o(1))k \log k$ |

[DZ02] | cycles | weighted graphs with no induced subdivision of $K_{2,3}$, a wheel, or an 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$ |

[RRST96] | directed cycles | any digraph | v | unspecified |

[MMP+19] | directed cycles | any digraph | v_{1/4} |
$O(k^4)$ |

[MMP+19] | directed cycles | any digraph | v_{1/2} |
$O(k^6)$ |

[RS96] | directed cycles | planar digraphs | v | $O(k\log(k)\log\log k)$ |

[RS96] + [GW96] | directed cycles | planar digraphs | v | $63k$ |

[GT11] | directed cycles | 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$ |

[KKKX20] | directed odd cycles | any digraph | v_{1/2} |
unspecified |

[HJW18] | cycles non homologous to zero | embedded graphs | 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 | v_{1/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 | v_{1/2} |
unspecified |

[HJW18] | odd cycles non homologous to zero | embedded graphs | v_{1/2} |
unspecified |

[Bir03] | cycles of length $\geq 4$ | graphs without 2 vertex-disjoint cycles of length $\geq 4$ | v | =4 |

[Bir03] | cycles of length $\geq 5$ | graphs without 2 vertex-disjoint cycles of length $\geq 5$ | v | =5 |

[BBR07] | cycles of length $\geq t$ | any | v | $(13+o_t(1))tk^2$ |

[FH14] | cycles of length $\geq t$ | any | v | $(6t+4+o_t(1))k\log k$ |

[MNŠW17] | cycles of length $\geq t$ | any | v | $6kt + (10 + o(1)) k \log k$ |

[BHJ16] | cycles of length $\geq t$ | any | e | $O(k^2 \log k + kt)$ |

[CJU19] | cycles of length $\geq t$ | any | e | $8k(t−1)(\log_2(kt) + 1)$ |

[HM13] | directed cycles of length $\geq 3$ | any digraph | v | unspecified |

[AKKW16] | directed cycles of length $\geq t$ | any digraph | v | unspecified |

### Cycles with prescribed vertices

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

Ref. | Guest class | Host class | T. | Gap at most |
---|---|---|---|---|

[KKM11] | $S$-cycles | any | v | $40k^2 \log k$ |

[PW12] | $S$-cycles | any | v/e | $O(k \log k)$ |

[KKL19] | $S$-cycles | graphs without two vertex-disjoint $S$-cycles | v | =4 |

[BJS17] | $S$-cycles of length at least $t$ | any | v | $O(tk\log k)$ |

[Joo14] | odd $S$-cycles | $50k$-connected graphs | v | $O(k)$ |

[KK13] | odd $S$-cycles | any | v_{1/2} |
unspecified |

[Bru19] | even $S$-cycles | any | e | unspecified |

[KK12] | directed $S$-cycles | all digraphs | v_{1/5} |
unspecified |

[KKKK13] | odd directed $S$-cycles | any digraph | 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$ |

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

[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)$ (note)The main result of [Liu17] is in fact stronger as is works for rooted subdivisions. See the paper for details. | any | 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] | \(\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 | 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$ |

[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 | v_{1/4} |
$\textrm{poly}(k,t)$ |

### Fractional packings

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

Ref. | Guest class | Host class | $k$ | $\tau$ | Relationship |
---|---|---|---|---|---|

[Sey95] | directed cycles | any digraph | max fractional vertex packing | min integral vertex covering | $\tau \leq 4k \ln(4k) \ln\log(4k)$ |

## Negative results

### Lower bounds for paths

Ref. | Guest class | Host class | T. | Gap at least |
---|---|---|---|---|

[MW15] | $H$-valid paths, $H$ with no matching of size $t$ | all graphs | v | unavoidable dependency in $t$ |

[BHJ18a] | $S$-paths of length $p \mod t$, for $t>4$ composite and fixed $p \in \{0, \dots, t-1\}$ | all graphs | v/e | arbitrary |

[BU18] | $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 |
---|---|---|---|---|

[Tuz90] | triangles | all graphs | e | $\geq 2k$ |

[Tuz90] | directed triangles | directed graphs without 3 edge-disjoint directed triangles | e | 3 |

[Lov65] | cycles | graphs without 2 vertex-disjoint cycles | v | =3 |

[Vos69] | cycles | graphs without 3 vertex-disjoint cycles | v | =6 |

[Vos67] (see [Vos69]) | cycles | graphs without 4 vertex-disjoint cycles | v | \geq 9 |

[EP65] | cycles | all graphs | v | $\Omega(k \log k)$ |

[Sim67] | cycles | all graphs | v | $> \left (\frac{1}{2} + o(1) \right ) k \log k$ |

[Vos69] (see [Vos68]) | cycles | all graphs | v | $\geq \frac{1}{8} k \log k$ |

[KLL02] | cycles | planar graphs | v | $\geq2k$ |

[MYZ13] | cycles | planar graphs | e | $\geq 4k-c$, $c\in \mathbb{R}$ |

[DNL87] [Ree99] | odd cycles | all graphs | v | arbitrary |

[DNL87] | cycles of length $p \mod t$, for every fixed $p \in \{1, \dots, t-1\}$ | all graphs | v | arbitrary |

[Ree99] | odd cycles | all graphs | e | arbitrary |

[Tho01] | odd cycles | planar graphs | v | $\geq 2k$ |

[KV04] | odd cycles | planar graphs | e | $\geq 2k$ |

[PW12] | $S$-cycles | all graphs | v | $\Omega(k\log k)$ |

[KKL19] | $S$-cycles | graphs without two disjoint $S$-cycles | v | =4 |

[KK13] | odd $S$-cycles | all graphs | v | arbitrary |

[Bru19] | even $S$-cycles of length $\geq \ell$, for every fixed $\ell \geq 5$ | all graphs | e | arbitrary |

[Bru19] | $S$-cycles of length $0 \mod t$, for every fixed $t > 2$ | all graphs | e | arbitrary |

[Sey95] | directed cycles | all digraphs | vActually proved for fractional packings | $\frac{1}{30} k \ln k$ |

[GW96]A simpler construction consists in a $C_5$ where every edge has been replaced by a directed triangle. | directed cycles | planar digraphs | v | $3/2$ |

[KK12] | directed $S$-cycles | all digraphs | v/e | arbitrary |

[KKKK13] | odd directed $S$-cycles | all digraphs | v | arbitrary |

[Bir03] | cycles of length $\geq 4$ | graphs without 2 vertex-disjoint cycles of length $\geq 4$ | v | =4 |

[Bir03] | cycles of length $\geq 5$ | graphs without 2 vertex-disjoint cycles of length $\geq 5$ | v | =5 |

[FH14] | cycles of length $\geq t$ | all graphs | v | $\Omega(k\log k)$, $t$ fixed |

[FH14] | cycles of length $\geq t$ | all graphs | v | $\Omega(t)$, $k$ fixed |

[MNŠW17] | cycles of length $\geq t$ | all graphs | v | $\geq(k-1)t$ |

[MNŠW17] | cycles of length $\geq t$ | all graphs | v | $\geq \frac{(k-1)\log k}{8}$ |

[BHJ16] | cycles of length $\geq t$ | all graphs | e | $O(k \log k + kt)$ |

[Sim67] | 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.
*Arxiv preprint arXiv:1710.06282*, 2017. - [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. - [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. - [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.
*Arxiv preprint arXiv:1809.11038*, October 2018. - [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;
*Arxiv preprint arXiv:1805.00426*, 2018. - [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.
*ArXiv preprint arXiv:1910.00642*, 2019. - [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.
*ArXiv preprint arXiv:1805.08673*, May 2018. - [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.
*arxiv preprint 1807.04969*, 2018. - [CJU19] Wouter Cames van Batenburg, Gwenaël Joret, and Arthur Ulmer. Erdős-Pósa from ball packing.
*ArXiv preprint arXiv:1912.07965*, 2019. - [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. - [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. - [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.
*ArXiv preprint arXiv:1908.09065*, 2019. - [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. arXiv preprint arXiv:1803.07581, 2018.
- [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.
*ArXiv preprint arXiv:1505.00867*, May 2015. - [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.
*Arxiv preprint arXiv:1806.08809*, June 2018. - [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. - [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. - [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.
*Arxiv preprint arXiv:1803.02703*(2018). - [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: August 2020.