1 Introduction↩︎

The main problem we address in this paper is whether a graph \(G\) contains many vertex-disjoint cycles of different lengths. Bensmail, Harutyunyan, Le, Li, and Lichiardopol [@BHLLL17] proved that the answer is yes for graphs with large minimum degree.

Rather than a sufficient condition, we instead prove a rough structure theorem for the set of graphs which do not contain many vertex-disjoint cycles of different lengths. The related problem of when a graph contains many vertex-disjoint induced cycles of different lengths was very recently considered by Chudnovsky and Maier [@chudnovsky2026induced]. Our theorem can be viewed as an Erdős-Pósa type theorem, which is a reference to the following classic result by Erdős and Pósa.

The Erdős-Pósa Theorem has been hugely influential in graph structure theory and has been studied in numerous other settings, including minors [@RobertsonS1986Graph; @CamesvanBatenburgHJR2019Tight; @PaulPTW2024Obstructions], topological minors [@Thomassen1988Presence; @Liu2022Packing; @PaulPTW2024Obstructions], immersions [@Liu2021Packing; @KK18], directed cycles [@ReedRST1996Packing], matroid circuits [@GK09], and vertex minors [@EPvertexminors].

Moreover, there is an extensive line of work on the Erdős-Pósa property for cycles satisfying various constraints including triangles [@tuza90], odd cycles [@Reed1999Mangoes; @KawarabayashiKKX2025Halfintegral], even cycles [@BruhnHJ2018Frames; @GorskyKKW2024Packing; @Gorsky2024Structure], cycles of length \(0 \pmod{m}\) [@Thomassen1988Presence], cycles of length \(\ell \pmod{p}\) with \(p\) prime [@ThomasY2023Packinga], long cycles [@BBR07; @CJU20; @MNSW17], holes [@KimK2020ErdHosPosa; @HK24], \(S\)-cycles [@KakimuraKM2011Packing], and \((S_1,S_2)\)-cycles [@HuynhJW2019Unified]. Most (but not all) of the aforementioned results on cycles now follow from very general theorems for cycles in graphs with edge-labels from multiple abelian groups [@HuynhJW2019Unified; @GollinHKOY2022Unified; @GollinHKKO2024Unified]. For more details, we refer the interested reader to [@RaymondT2017Recent] for a general survey on Erdős-Pósa theorems.

All of the above results can be stated in terms of packings and covers in hypergraphs, as we now describe. Given a hypergraph \(H\), a packing is a set of disjoint hyperedges, and a cover is a set of vertices \(X\) such that \(e \cap X \neq \emptyset\) for all \(e \in E(H)\). We define \(\nu(H)\mathrel{\vcenter{:}}=\max\{|M| : \text{M is a packing}\}\) and \(\tau(H)\mathrel{\vcenter{:}}=\min\{ |X| : \text{X is a cover}\}\). Clearly, \(\tau(H) \geq \nu(H)\) for every hypergraph \(H\). We say that a family \(\mathcal{H}\) of hypergraphs satisfies the Erdős-Pósa property if there exists a function \(f\) such that \(\tau(H) \leq f(\nu(H))\) for every \(H \in \mathcal{H}\). For example, for every graph \(G\), we can make a hypergraph \(H_G\), where \(V(H_G)=V(G)\) and \(E(H_G)=\{V(C) \mid \text{C is a cycle of G}\}\). The original theorem of Erdős and Pósa is simply the assertion that the family of hypergraphs \(\mathcal{H}\mathrel{\vcenter{:}}=\{H_G \mid \text{G is a graph}\}\) has the Erdős-Pósa property. Moreover, maximum packings and minimum covers are optimal integral solutions to two dual linear programs, and the Erdős-Pósa function \(f\) measures the integrality gap between the two linear programs.

Interestingly, maximising the number of vertex-disjoint cycles of different lengths in a graph \(G\) is not a maximum packing problem in a hypergraph with vertex set \(V(G)\). Thus, our main problem does not fit into the above framework. Nonetheless, we provide another type of “dual certificate” whenever a graph does not contain \(k\) vertex-disjoint cycles of different lengths. Our dual certificate is stated in terms of the cycle spectrum \(\Lambda(G)\) of a graph \(G\), defined as \(\Lambda(G)\mathrel{\vcenter{:}}=\{ \ell \in \mathbb{N} \mid \text{G contains a cycle of length \ell}\}\). The cycle spectrum of a graph has been extensively studied (see the surveys [@cyclespectrum; @BGS22]). For example, Bondy’s famed meta-conjecture [@bondy71] asserts that every non-trivial condition implying that a graph \(G\) is Hamiltonian actually implies that \(\Lambda(G)=\{3, \dots, |V(G)|\}\) (with some simple family of exceptions).

The following is our first main result.

Note that for every \(X \subseteq V(G)\), the number of vertex-disjoint cycles of distinct lengths is at most \(|\Lambda(G-X)|+|X|\). In particular, the set \(X\) from certifies that \(G\) contains \(\mathcal{O}(k^6\mathsf{polylog}(k))\) vertex-disjoint cycles of different lengths. In we show that the bound \(|\Lambda(G-X)| \leq k-1\) in is best possible even for arbitrarily large \(X\).

We also prove analogous results for facial cycles of embedded graphs. In fact, we prove a more general theorem where faces are “coloured” (not necessarily by their length), and we seek facial cycles with distinct colours that are also pairwise far apart. Precise definitions will be given later in .

Theorems 3 and 4 are rare instances of Erdős-Pósa theorems which cannot be naturally phrased as a maximum packing versus minimum cover problem in a hypergraph. Other notable examples include the recent Erdős-Pósa theorems in the emerging field of “coarse graph theory” [@AHJKW24; @GP25; @AGHK25; @DJMM24].

We achieve our bounds for the size of the hitting set in  by analysing the cycle spectrum of ladder-like graphs, whose presence we can guarantee given high enough treewidth. Using a construction from additive combinatorics, we also prove that there are subdivided ladders whose cycle spectrum is small. In the following statement, the \(k\)-ladder is defined as the Cartesian product of \(K_2\) and a \(k\)-vertex path.

suggests that different techniques are required to improve the bound in .

Paper Outline. We begin by proving the non-algorithmic version of  in , with the necessary arguments for the algorithmic part being deferred to . In , we provide constructions giving lower bounds for . We then prove  in  and in . Finally, in , we discuss possible extensions of our main results, focusing primarily on counterexamples across various settings.

2 Disjoint cycles with distinct lengths↩︎

The proofs in this section rely heavily on the graph minor structure theory of Robertson and Seymour, in particular on treewidth and arguments on tree-decompositions.

Let us first define what we mean by a tree-decomposition. A tree-decomposition of a graph \(G\) is a pair \(\mathcal{T} = (T, \beta)\), where \(T\) is a tree and \(\beta \colon V(T) \rightarrow 2^{V(G)}\) such that

• for every edge \(e \in E(G)\), there exists a \(t \in V(T)\) such that \(e \subseteq \beta(t)\), and

• for every vertex \(v \in V(G)\), the set \(\beta^{-1}(v)\) induces a connected, non-empty subtree of \(T\).

The width of \(\mathcal{T}\) is the maximum value of \(|\beta(t)| - 1\) over all \(t \in V(T)\) and the treewidth \(\mathsf{tw}(G)\) of \(G\) is the minimum width over all tree-decompositions of \(G\).

If \(T\) has a designated root \(r\), we call \((T,r,\beta)\) a rooted tree-decomposition. Given a tree \(T\) with a root \(r\) and a vertex \(t \in V(T)\), we denote by \(T_t\) the subtree of \(T\) that contains all vertices whose path to \(r\) in \(T\) contains \(t\). Further, if \((T,r,\beta)\) is a rooted tree-decomposition of a graph \(G\), we denote by \(G_t\) the subgraph \(G[\bigcup_{s \in V(T_t)} \beta(s)]\).

We first show that graphs with bounded treewidth have our desired packing-covering property for cycles of distinct lengths. This is derived from the following lemma.

Applying the above lemma to an optimal tree-decomposition of \(G\) yields the following corollary.

Our next goal is to prove that in graphs of high treewidth, we can find a subgraph certifying the existence of many vertex-disjoint cycles of distinct lengths. One approach is to use the grid theorem of [@RobertsonS1986Grapha] (see [@ChuzhoyT2021Tighter] for the currently best-known bounds), which shows that a graph with high treewidth must contain a subdivision of a large wall. It is not too difficult to show that every subdivision of a sufficiently large wall contains many vertex-disjoint cycles of distinct lengths.

However, to obtain better bounds, we bypass using the grid theorem and aim for a different subgraph certifying the existence of many vertex-disjoint cycles of distinct lengths. Let \(k \in \mathbb{N}^+\). The \(k\)-prism is the Cartesian product of \(K_2\) and the cycle of length \(k\). Birmelé, Bondy, and Reed [@prisms] showed that every graph of treewidth \(\Omega(k^2)\) contains a subdivision of the \(k\)-prism.

Next, we show that every subdivision of a large prism contains many (not necessarily disjoint) cycles of distinct lengths.

Finally, we need a result of Chekuri and Chuzhoy [@chekuriC2013largetreewidth] on high treewidth partitions.

Together with  this yields the following corollary.

We are now ready to prove a non-algorithmic version of .

An algorithmic proof of this theorem is provided in .

3 Lower bounds↩︎

In order to quantify the tightness of our bounds, we introduce the following definition. Let \(f\) and \(g\) be functions \(\mathbb{N} \to \mathbb{R}\). We say that \((f,g)\) is a binding pair if for all \(k \in \mathbb{N}\), every graph \(G\) contains \(k\) vertex-disjoint cycles of distinct lengths, or a set of at most \(f(k)\) vertices \(X\) such that \(|\Lambda(G-X)| \leq g(k)\). We can restate our main theorem in terms of binding pairs as follows.

We now show that \(g(k)=k-1\) is optimal for binding pairs \((f,g)\) in the following strong sense.

On the other hand, we now show that \(f(k) \in \mathcal{O}(k \log k)\) is best possible for binding pairs \((f,g)\) in the following strong sense.

4 Coloured faces of embedded graphs↩︎

For our second main theorem, our goal is to pack or cover faces with distinct lengths in embedded graphs. We, in fact, prove a more general theorem for coloured faces, where the colour of a face is not necessarily equal to its length. We begin by reviewing some basic definitions from topological graph theory. We refer the reader to [@MoharT2001Graphs] for more details. The Euler genus of a surface obtained from the sphere by \(h\) handles and \(c\) crosscaps is \(2h+c\).

4.1 Embedded graphs, surfaces, and colouring↩︎

4.1.0.1 Embeddings

Given a graph \(G\), we say that \(G\) has an embedding \(\psi\) into a surface \(\Sigma\), if \(\psi\) is a function with domain \(V(G) \cup E(G)\) such that

1. \(\psi(v)\) is a point of \(\Sigma\) for each \(v \in V(G)\),

2. \(\psi(u) \neq \psi(v)\) for all distinct \(u,v \in V(G)\),

3. \(\psi(uv)\) is a simple curve in \(\Sigma\) with the ends \(\psi(u),\psi(v)\) for all \(uv \in E(G)\),

4. \(\psi(uv) \cap \psi(wx) \subseteq \{ \psi(u), \psi(v) \}\), for all distinct \(uv, wx \in E(G)\), and

5. \(\psi(uv) \cap \psi(w) = \emptyset\) for all \(uv \in E(G)\) and \(w \in V(G) \setminus \{ u,v \}\).

We let \(\psi(G)\) be the union of all points and curves in its image and call the connected components of \(\Sigma \setminus \psi(G)\) the faces of \(\psi\), and we let \(\mathcal{F}(\psi)\) be the set of faces of \(\psi\). If every face of \(\psi\) is homeomorphic to an open disk, we say that \(\psi\) is a 2-cell embedding. If, in addition, the boundary of each face is a simple closed curve, then \(\psi\) is a closed 2-cell embedding.

A particular advantage of closed 2-cell embeddings is that they allow us to define simple dual graphs of embedded graphs. Let \(G\) be a graph with a closed 2-cell embedding \(\psi\) in some surface. Then the dual graph \(G^*\) of \(G\) is a graph with vertex set \(\mathcal{F}(\psi)\) and the edge \(FF' \in E(G^*)\) if the facial cycles of the faces \(F\) and \(F'\) of \(\psi\) intersect in an edge. Under our assumptions, \(G^*\) is a simple graph [@MoharT2001Graphs]. We generally drop the reference to \(\psi\), as in our applications, the embedding is clear from the context. By a slight abuse of notation, we let \(V(F)\) be the vertices of \(G\) which are on the boundary of \(F\).

4.1.0.2 Colouring graphs on surfaces.

Given an integer \(k\) and a set \(S\), we say that a function \(c \colon S \to [k]\) is a \(k\)-colouring of \(S\). If we do not want to specify \(k\), we simply call \(c\) a colouring of \(S\). Note that we have no further requirements on \(c\). If \(c\) is a colouring of the vertex set \(V(G)\) of a graph \(G\), we call \(c\) proper if for all edges \(uv \in E(G)\) we have \(c(u) \neq c(v)\). A graph \(G\) is \(k\)-colourable if there exists a proper \(k\)-colouring of \(V(G)\) and we denote by \(\chi(G)\) the minimum number \(\ell\) such that \(G\) has a proper \(\ell\)-colouring.

We also need the following classic result on colouring embedded graphs, which is a combination of the Four Colour Theorem [@AppelH1976Every; @AppelH1976Existence; @AppelH1977Every; @AppelHK1977Every] and Heawood’s classic result on colouring graphs embedded on surfaces other than the sphere [@Heawood1890MapColour].

4.2 Packing and covering coloured faces↩︎

We begin with a warm-up exercise. Since deleting a vertex on a face creates a new face not found in the original graph, we use the packing and covering framing for the Erdős-Pósa property that we presented in the introduction instead of deleting vertices.

To see how this is related to our previous questions, we can define the colour of a face to be its length. now tells us that we can pack \(k\) pairwise edge-disjoint facial cycles of different lengths, or the set of face lengths of \(G\) is already small.

The proof of does not generalise directly to vertex-disjoint facial cycles, which tells us that the dual graph misses some face intersections, namely those that consist of a single vertex. We thus define a notion of distance for faces of embedded graphs which captures this.

Let \(G\) be a graph with a 2-cell embedding \(\psi\) on a surface \(\Sigma\) of Euler genus \(g\). Further, let \(G_\mathcal{F}\) be the graph with vertex set \(\mathcal{F}(\psi)\) such that two faces \(F, F'\) are adjacent if and only if \(V(F) \cap V(F') \neq \emptyset\). We call \(G_\mathcal{F}\) the face-incidence graph of \(G\) and \(\psi\). We let the distance in \(\psi\) between two faces \(F,F' \in \mathcal{F}(\psi)\) be the distance between \(F\) and \(F'\) in \(G_\mathcal{F}\).

We further need to define the radial graph \(R(G,\psi)\) of a graph \(G\) with a 2-cell embedding \(\psi\) on some surface \(\Sigma\). We construct \(R(G,\psi)\) from \(G\) by adding a vertex \(v_F\) for each \(F \in \mathcal{F}(\psi)\) and then adding the edges \(v_Fu\) for all \(F \in \mathcal{F}(\psi)\) and all \(u \in V(F)\). We note that \(\psi\) can be extended to an embedding of \(R(G,\psi)\) in \(\Sigma\) by placing \(v_F\) into \(F\) and drawing the additional edges incident to \(v_F\) inside \(F\) in the natural fashion. Note that if \(F\) and \(F'\) are at distance \(d\) in the face-incidence graph \(G_\mathcal{F}\), then \(v_F\) and \(v_{F'}\) are at distance at most \(2d\) in \(R(G,\psi)\).

For any given graph \(G\), integer \(r \in \mathbb{N}\), and \(v \in V(G)\), we let \(N^r_G(v)\) be the \(r\)-neighbourhood of \(v\) (in \(G\)), which is the set of all vertices in \(V(G)\) that lie at distance at most \(r\) from \(v\) in \(G\). Note that for all \(r \in \mathbb{N}\) and \(v \in V(G)\), we thus have \(v \in N^r_G(v)\). For \(X \subseteq V(G)\), we let \(N^r_G(X)\) denote \(\bigcup_{x \in X} N^r_G(x)\).

We say that a graph \(G\) has local treewidth at most \(f\) if \(f: \mathbb{N} \rightarrow \mathbb{N}\) is a function such that for any vertex \(v \in V(G)\), we have \(\mathsf{tw}(G[N^d(v)]) \leq f(d)\). Eppstein showed that a minor-closed class of graphs has bounded local treewidth if and only if it does not include all apex-graphs [@Eppstein2000Diameter] (see also [@HendreyW2025Polynomial] for recent improvements giving polynomial bounds). We use in particular that graphs of bounded genus have bounded local treewidth, as given below.

We derive from a more general fact about packing far apart vertices of distinct colours, see . Before we prove this, we first state an analogue of the algorithmic version of . A proof of this statement is provided in .

We now use the above lemma to get a similar result for graphs that only locally have low treewidth.

We note that  does not generalise to the class of all graphs. Consider a subdivided clique so that every pair of high degree vertices lies at distance \(d-1\). Colour every original vertex by a unique colour, and every subdividing vertex by a single colour. This graph contains no 3 vertices of pairwise distance \(d\) and of distinct colours, yet \(|X|\) and the number of remaining vertices must grow with the size of the clique.

We also note that the following approximate converse of holds.

Hence, if \(d\) is odd, the second outcome of implies that there is no packing of \(\mathcal{O}(k^2f(2d))\) vertices of distinct colours and with pairwise distance \(d\).

We can now obtain , which we restate here, with little additional effort.

Note that applying the above with \(d=1\), meaning that we want vertex-disjoint faces, yields a hitting set of balls of radius 1 instead of single vertices. However, we can easily rectify this by a slight modification of the proof. If \(X\) is the set returned by , then for every vertex \(x \in X\), if \(x = v_F\) for some face \(F\), then \(N^1(x)\) only covers that singular face vertex, so we may replace \(x\) by an arbitrary vertex of \(V(F)\). If instead \(x \in V(G)\), then \(x\) only covers \(v_F\) for \(F\) such that \(x \in V(F)\). Hence, this single vertex is enough to hit all the corresponding faces. This gives the following corollary.

Finally, we remark that in the proof of , we use that the neighbourhood around a vertex has bounded treewidth. But the neighbourhood around a facial cycle also has bounded treewidth, as for any facial cycle \(F\), we have \(N_G^d(V(F)) \subseteq N^d_{R(G,\psi)}(v_F)\). Thus, by following the same proof as for , we may also obtain the following result.

5 Subdivided ladders with few cycle lengths↩︎

Recall that the \(k\)-ladder is the Cartesian product of \(K_2\) and a path with \(k\) vertices. Note that a \(k\)-ladder is a subgraph of a \(k\)-prism. However, unlike prisms, a \(k\)-ladder is a subgraph of an \(\ell\)-ladder for every \(\ell \geq k\). Therefore, a natural approach to improve the bound in our main theorem is to use \(k\)-ladders instead of \(k\)-prisms in .

Observe that the Erdős-Szekeres theorem implies a bound of \(\Omega(\sqrt{k})\) in . By partitioning a \(k^2\)-ladder into \(k\) disjoint \(k\)-ladders, we also note that a positive answer to implies a positive answer to the following.

Because every graph with treewidth \(\Omega(k^4)\) contains a subdivided \(k^2\)-ladder, a positive answer to would improve the bound on \(|X|\) in  from \(\mathcal{O}(k^6\mathsf{polylog}(k))\) to \(\mathcal{O}(k^5)\). Unfortunately, we now show that both  have negative answers. The counterexample utilises the following result in additive combinatorics. For a finite set \(A \subseteq \mathbb{Z}\), define the sum set \(A + A \mathrel{\vcenter{:}}= \{a + b \mid a, b \in A\}\) and the difference set \(A - A \mathrel{\vcenter{:}}= \{a - b \mid a, b \in A\}\). A construction by Hennecart, Robert, and Yudin [@HennecartRY99] yields sets \(A\) that have a significantly larger difference set than sum set. In the following statements, we fix a constant \(C \mathrel{\vcenter{:}}= \frac{\log 2}{\log (1 + \sqrt{2})} < 0.7865\).

We use  to create a finite point set \(P \subseteq \mathbb{Z}^2\) in the two-dimensional plane with specific properties. We shall say that \(P\) is a constellation if all points in \(P\) have pairwise different \(x\)-coordinates, namely, \(x_1 \neq x_2\) for all distinct \((x_1, y_1), (x_2, y_2) \in P\). For two points \(p_1 = (x_1, y_1)\), \(p_2 = (x_2, y_2)\), define \(d(p_1, p_2) = y_1 + y_2 + |x_1 - x_2|\). The variety of a constellation \(P\) is the number of different values of \(d(p_1, p_2)\) for distinct \(p_1, p_2 \in P\), i.e., \[|\{ d(p_1, p_2) \mid p_1, p_2 \in P,\, p_1 \neq p_2 \}|.\] We now show that the variety of a constellation can be significantly smaller than its cardinality.

To prove , we now translate the constellation of  into a subdivision of a ladder with few cycle lengths.

This refutes . It remains to refute . This follows immediately from the following statement.

We note that also shows that there exist subdivided \(k^2\)-prisms with at most \(\mathcal{O}(k^{0.8806})\) vertex-disjoint cycles of distinct lengths.

6 On possible extensions of our results↩︎

6.0.0.1 Improved bounds.

Given , it appears quite challenging to improve our bounds without completely new ideas. Nonetheless, the following conjecture could be true.

By , would be simultaneously optimal for both \(|X|\) and \(|\Lambda(G-X)|\). Moreover, the transformation presented in the proof of shows that also implies the classic Erdős-Pósa theorem.

It is also natural to ask if our results can be extended to lengths which are not only distinct but also satisfy some additional nice properties. This appears quite challenging given the following negative results.

6.0.0.2 Consecutive lengths.

Does there exist a function \(f(k)\) such that every graph \(G\) contains \(k\) vertex-disjoint cycles whose lengths are \(k\) consecutive integers or a set \(X\) of at most \(f(k)\) vertices such that \(\Lambda(G-X)\) does not contain \(f(k)\) consecutive integers? The following simple example shows that the answer is negative. Let \(C_a\) denote the cycle of length \(a\). Given \(A \subseteq \mathbb{N}\), let \(G_A=\bigcup_{a \in A} C_a\), where there exists a vertex \(x \in V(G_A)\) such that \(V(C_a) \cap V(C_b)=\{x\}\) for all distinct \(a,b \in A\). Let \(\mathcal{A}\) be a family of subsets of \(\mathbb{N}\) such that each \(A \in \mathcal{A}\) is a large subset of consecutive integers and \(A \cup A'\) is not a set of consecutive integers for all distinct \(A, A' \in \mathcal{A}\). Let \(G_{\mathcal{A}}\) be the disjoint union of \(G_A\), over all \(A \in \mathcal{A}\). Note that \(G_\mathcal{A}\) does not contain two vertex-disjoint cycles of consecutive lengths. On the other hand if \(|X| < |\mathcal{A}|\), then \(\Lambda(G_{\mathcal{A}}-X)\) still contains long sequences of consecutive integers (since \(X \cap V(G_A)=\emptyset\) for some \(A \in \mathcal{A}\)). This example actually shows that for all \(t \in \mathbb{N}\), the \(\frac{1}{t}\)-integral Erdős-Pósa property fails for consecutive cycle lengths.

6.0.0.3 Arithmetic Progressions.

What if instead of asking for consecutive lengths, we ask for lengths which form an arithmetic progression? There are two natural ways to formalise this question, depending on whether we fix the common difference of the arithmetic progression or not. To be precise, recall that a \(d\)-arithmetic progression is a sequence of integers whose consecutive terms differ by \(d\). A sequence is an arithmetic progression if it is a \(d\)-arithmetic progression for some \(d\). Fix \(d \geq 1\). Does there exist a function \(f(k)\) such that every graph \(G\) contains \(k\) vertex-disjoint cycles whose lengths form a \(d\)-arithmetic progression or a set of at most \(f(k)\) vertices \(X\) such that \(\Lambda(G-X)\) does not contain a \(d\)-arithmetic progression of size \(f(k)\)? Alternatively, we can allow \(d\) to vary. That is, does there exist a function \(f(k)\) such that every graph \(G\) contains \(k\) vertex-disjoint cycles whose lengths form an arithmetic progression or a set of at most \(f(k)\) vertices \(X\) such that \(\Lambda(G-X)\) does not contain any arithmetic progression of size \(f(k)\)?

A slight modification of the previous counterexample shows that the answer is negative for both questions. For the first question, this is straightforward by taking a \((d-1)\)-subdivision of the previous counterexample. For the second question, we say that a family \(\mathcal{A}\) of subsets of \(\mathbb{N}\) is \((p,\ell)\)-good if each \(A \in \mathcal{A}\) is a \(p\)-arithmetic progression of length \(\ell\) and every arithmetic progression of length at least 3 in \(\bigcup \mathcal{A}\) is a subset of \(A\) for some \(A \in \mathcal{A}\). We claim that for all \(p,\ell \in \mathbb{N}\), there exist arbitrarily large \((p,\ell)\)-good families. To see this, observe that if \(\mathcal{A}\) is \((p,\ell)\)-good, then \(\mathcal{A} \cup \{A\}\) is \((p,\ell)\)-good, where \(A\) is a \(p\)-arithmetic progression of length \(\ell\) whose smallest element is at least triple the maximum element of \(\bigcup \mathcal{A}\). Let \(\mathcal{A}\) be a large \((p,\ell)\)-good family, with \(p\) arbitrary and \(\ell\) large. Then the graph \(G_{\mathcal{A}}\) (as defined above) does not contain three vertex-disjoint cycles whose lengths form an arithmetic progression, but \(\Lambda(G_{\mathcal{A}}-X)\) contains an arithmetic progression of length \(\ell\) for all \(X\) with \(|X| < |\mathcal{A}|\).

6.0.0.4 Prescribed lengths.

Given a subset \(L \subseteq \mathbb{N}\), do there exist functions \(f_L : \mathbb{N} \to \mathbb{N}\) and \(g_L : \mathbb{N} \to \mathbb{N}\) such that every graph \(G\) contains \(k\) vertex-disjoint cycles with distinct lengths from \(L\) or a set \(X\) of at most \(f_L(k)\) vertices such that \(|\Lambda(G-X) \cap L| \leq g_L(k)\)? In recent work, Gorsky, Hendrey, and Huynh [@GorskyHH2026ErdosPosa] show that \(f_L\) and \(g_L\) do not exist if \(L\) is the set of prime numbers. More generally, they prove that \(f_L\) and \(g_L\) do not exist if \(L\) is infinite and \(\mathbb{N} \setminus L\) contains arbitrarily long sequences of consecutive integers.

6.0.0.5 Directed graphs.

In a completely different direction, one can also ask if our results hold for digraphs. We discuss only the simplest version of this. In particular, is it true that there exists a function \(g(k)\) such that every digraph \(D\) contains \(k\) vertex-disjoint directed cycles of different lengths or a set \(X\) of at most \(g(k)\) vertices such that \(D-X\) contains at most \(g(k)\) different directed cycle lengths? It turns out that this is false, as the following counterexample shows.

Suppose there was such a function \(g(k)\). We construct a subdivision of a large cylindrical grid in which all cycles have the same length in the following way. We consider a planar embedding of a cylindrical grid such that all cycles are embedded counterclockwise around a point \(x\) in the plane and for every edge \(e\) there is a positive counterclockwise angle \(w(e) \in [360]\) between the straight line of its start-vertex to \(x\) and the straight line from its end-vertex to \(x\), see .

Now we subdivide every edge according to the angle we just described, making it a path of length \(w(e)\). This way, every cycle has length exactly \(360\).

Now, we attach many paths to the outermost cycle of the grid of such that each path begins at the end-vertex of an out-path of the grid ends at the start-vertex of the next in-path. Moreover, the lengths of the newly attached paths are all distinct and larger than 360.

Now there are no three disjoint cycles of different lengths. However, for every set \(X\) of size \(g(k)\), \(G-X\) still contains many distinct cycle lengths.

Since the most basic form of our type of question has a negative answer, it is natural to relax its conditions and ask whether a half-integral variant, in which cycles may share vertices to a limited extent, may hold. Such half-integral versions of the Erdős-Pósa property for directed cycles often hold, despite the integral versions failing on very similar counterexamples (see [@GorskyKKW2024Packing; @Gorsky2024Structure; @KawarabayashiKKX2025Halfintegral]).

Finally, for the sake of completeness, we note that the directed version of is famously open and not yet known to hold for any minimum out-degree condition depending only on \(k\).

6.0.0.6 \(H\)-minor-free graphs.

In a different direction than cycles, it is natural to ask whether holds more generally for \(H\)-minor-free graphs. That is, we leave the following as an open problem.

It is not too hard to see how to do this “locally” by using . Graphs with a forbidden \(H\)-minor have a tree-decomposition into parts such that every part has bounded local treewidth after deleting a small number of apices (see [@Grohe2003Local]). Thus, for a single part, we can recolour all vertices within distance \(\lfloor d/2\rfloor\) from the apices by a single special colour and apply , and then we can add these apices to any hitting set. It is unclear how to extend these local solutions “globally” along the entire tree-decomposition.

6.0.0.7 Acknowledgements:

Much of the research presented here was carried out whilst a subset of the authors were attending the BWAG workshop in Bertinoro that took place in September of 2025 and the 2026 Barbados Graph Theory Workshop. We thank the organisers and other participants of both workshops for providing productive atmospheres to work in.

7 An algorithmic proof of ↩︎

We now present an algorithmic proof of . The key ingredient is the following theorem of Visser and Bodlaender [@visserbodlaender], which shows that the cycle spectrum of a graph can be computed in fixed-parameter time in graphs of treewidth at most \(k\).

If one does not care about the dependence on \(\ell\), then  also follows from a version of Courcelle’s Theorem [@courcellemosbah], which can output the set of all possible sizes of a set \(X\) satisfying an MSO-formula \(\varphi\) on bounded treewidth graphs.

We also need to efficiently find cycles of each length in the cycle spectrum of a graph with bounded treewidth. The algorithm of Visser and Bodlaender [@visserbodlaender] does not output these cycles, although it can probably be adapted to do so. However, the following naive approach works, at the cost of a slightly worse runtime.

Finally, we also require the following elementary fact about (rooted) tree-decompositions.

This brings us to the promised algorithmic version of .

By combining  with , we obtain an algorithmic version of  with runtime \(\mathcal{O}(18^{k^5} \mathsf{poly}(k) |V(G)|^7)\), as claimed.

8 Proof of ↩︎

Here we present the proof of . We use the following state-of-the-art algorithm to compute a tree-decomposition of width at most \(k\).

---

1. FAMNIT, University of Primorska, Koper, Slovenia. Supported by the Slovenian Research and Innovation Agency (research project N1-0370).↩︎

2. Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea. Supported by the Institute for Basic Science (IBS-R029-C1).↩︎

3. Technical University Darmstadt, Darmstadt, Germany↩︎

4. School of Mathematics, Monash University, Melbourne, Australia. Supported by the Australian Research Council↩︎

5. School of Mathematics, Georgia Institute of Technology, Atlanta, USA. Supported in part by the Georgia Tech ARC-ACO Fellowship and in part by the National Science Foundation under Grant No. DMS-2452111.↩︎

6. Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany↩︎

7. School of Computing, KAIST, Daejeon, South Korea↩︎

8. Sapienza University of Rome, Rome, Italy↩︎

9. pascal.gollin@famnit.upr.si, m.gorsky@pm.me, research@meikehatzel.com, kevin.hendrey1@monash.edu, tony@ibs.re.kr, cmcfarland30@gatech.edu, msokolow@mpi-inf.mpg.de, wiederrecht@kaist.ac.kr, wollan@di.uniroma1.it.↩︎