Erdős–Pósa-type conjecture for cycles of distinct lengths

Less than 1 year old · traced to

For a graph GG, let Λ(G)={ℓ∈N∣G contains a cycle of length ℓ}\Lambda(G)=\{\ell\in\mathbb{N}\mid G\text{ contains a cycle of length }\ell\}, and let G−XG-X denote the graph obtained by deleting the vertices in XX. Distinct-length cycle packing-cover conjecture. There exists a function f(k)∈O(klog⁡k)f(k)\in\mathcal{O}(k\log k) such that every graph GG contains kk vertex-disjoint cycles with distinct lengths, or a set XX of at most f(k)f(k) vertices such that

∣Λ(G−X)∣≤k−1.|\Lambda(G-X)|\leq k-1.

This proposes an Erdős–Pósa-type dual certificate for cycles of pairwise distinct lengths; the source presents it as a possible improvement and does not state that it has been resolved.

References

Primary source

J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel, Kevin Hendrey, Tony Huynh, Caleb McFarland, Marek Sokołowski, Sebastian Wiederrecht and Paul Wollan, “An Erdős-Pósa theorem for cycles and faces of distinct lengths”, arXiv:2607.06869 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.