An Erdős-Pósa Theorem for Cycles and Faces of Distinct Lengths

Jul 16, 2026

The paper establishes an Erdős-Pósa type result for graphs containing many vertex-disjoint cycles of pairwise distinct lengths. For every k∈N, either a graph G has k such cycles, or there is a vertex set X with size O(k^6 polylog(k)) so that G−X contains at most k−1 different cycle lengths. Analogous theorems are proved for facial lengths in embedded graphs, including distance and color constraints. It also applies additive combinatorics to obtain subdivided ladders with few cycle lengths, indicating the bounds are likely hard to substantially improve.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages25

Reading Time1 h 3 min

Introduction

Problem and context

Erdős-Pósa background via hypergraphs

arXiv :2607 .06869v1 [math .CO] 8 Jul 2026 An Erdős-Pósa theorem for cycles and faces of distinct lengths ∗ J. Pascal Gollin† Maximilian Gorsky‡ Meike Hatzel § Kevin Hendrey¶ Tony Huynh‡ Caleb McFarland‖ Marek Sokołowski∗∗ Sebastian Wiederrecht†† Paul Wollan‡‡ We show that for every k ∈ N, every graph G contains k vertex-disjoint cycles of different lengths, or there exists a set X ⊆ V (G) with |X| ∈ O (k6 polylog (k)) such that G − X has at most k − 1 cycle lengths. We also prove analogous results for facial lengths of embedded graphs. Let G be a graph with a closed 2-cell embedding ψ on a surface Σ of Euler genus g, let c be a colouring of the faces F (ψ) of ψ, and let R (G, ψ) be the radial graph of (G, ψ) . Then there exist k faces F1 , . . . , Fk ∈ F (ψ) that are given pairwise distinct colours by c and are pairwise at distance at least d in ψ, or there exists a set X ⊆ V (G) of order at most O (k2 dg) such that |{c(F ) | F ∈ F (ψ) and V (F ) ∩Sx∈X NdR(G,ψ)(x) = ∅}| ≤ k (k + 2) . Finally, using a result from additive combinatorics, we show that there are subdivided ladders with only a small number of cycle lengths. This suggests that it may be difficult to improve our bounds. ∗ [pascal.gollin@famnit.upr.si](pascal.gollin@famnit.upr.si), [m.gorsky@pm.me](m.gorsky@pm.me), [research@meikehatzel.com](research@meikehatzel.com), [kevin.hendrey1@monash.edu](kevin.hendrey1@monash.edu), [tony@ibs.re.kr](tony@ibs.re.kr), [cmcfarland30@gatech.edu](cmcfarland30@gatech.edu), [msokolow@mpi-inf.mpg.de](msokolow@mpi-inf.mpg.de), [wiederrecht@kaist.ac.kr](wiederrecht@kaist.ac.kr), [wollan@di.uniroma1.it](wollan@di.uniroma1.it). †FAMNIT, University of Primorska, Koper, Slovenia. Supported by the Slovenian Research and Innovation Agency (research project N1-0370) . ‡Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea. Supported by the Institute for Basic Science (IBS-R029-C1) . § Technical University Darmstadt, Darmstadt, Germany ¶ School of Mathematics, Monash University, Melbourne, Australia. Supported by the Australian Research Council ‖ 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 .∗∗ Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany ††School of Computing, KAIST, Daejeon, South Korea ‡‡Sapienza University of Rome, Rome, Italy 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 [BHL+17] proved that the answer is yes for graphs with large minimum degree. Theorem 1.1 (Bensmail et al. [BHL+17]) . For every k ≥ 1, every graph of minimum degree at least 5~~k~~2~~ ~~+52~~k~~−2 contains k vertex-disjoint cycles of different lengths. 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 [CM26] . 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. Theorem 1.2 (Erdős-Pósa Theorem [EP65]) . There exists a function f (k) ∈ O (k log k) such that the following holds. For every k ∈ N and every graph G, G contains k vertex-disjoint cycles, or there exists a set X ⊆ V (G) with |X| ≤ f (k) such that G − X is a forest. The Erdős-Pósa Theorem has been hugely influential in graph structure theory and has been studied in numerous other settings, including minors [RS86b, CHJR19 , PPTW24], topological minors [Tho88, Liu22 , PPTW24], immersions [Liu21, KK18], directed cycles [RRST96], matroid circuits [GK09], and vertex minor

FAQs

What is the main Erdős-Pósa type claim about cycles of distinct lengths?

For every k, every graph either contains k vertex-disjoint cycles whose lengths are pairwise different, or admits a vertex deletion set X of size O(k^6 polylog(k)) after which the remaining graph has at most k−1 different cycle lengths.

How does the result extend to embedded graphs and facial lengths?

For a graph with a closed 2-cell embedding, either there are k faces with pairwise distinct colors and large pairwise distance in the embedding, or there is a vertex set X of controlled size so that only limited colored faces remain outside neighborhoods in the radial graph.

Why are additive combinatorics tools used, and what do they produce?

Using an additive combinatorics result, the paper shows the existence of subdivided ladders whose cycle-length set is small. This motivates why the current bounds may be difficult to improve.

Jul 16, 2026

Upload by Theodore