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

arXivarxiv/2607.06869Jul 8, 2026math.COscore 0

We show that for every $k \in \mathbb{N}$, every graph $G$ contains $k$ vertex-disjoint cycles of different lengths, or there exists a set $X \subseteq V(G)$ with $|X| \in \mathcal{O}(k^6\mathsf{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 $\mathcal{F}(ψ)$ of $ψ$, and let $R(G,ψ)$ be the radial graph of $(G, ψ)$. Then there exist $k$ faces $F_1, \ldots , F_k \in \mathcal{F}(ψ)$…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2607.06869
curl -X POST /api/v1/records/arxiv/2607.06869/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.06869/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'