An Erdős-Pósa theorem for cycles and faces of distinct lengths

Abstract

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 $\psi$ on a surface $\Sigma$ of Euler genus $g$, let $c$ be a colouring of the faces $\mathcal{F}(\psi )$ of $\psi$, and let $R(G,\psi )$ be the radial graph of $(G,\psi )$. Then there exist $k$ faces $F_1,\dots ,F_k\in \mathcal{F}(\psi )$ that are given pairwise distinct colours by $c$ and are pairwise at distance at least $d$ in $\psi$, or there exists a set $X\subseteq V(G)$ of order at most $\mathcal{O}(k^{2}dg)$ such that $|\{c(F)\mid F\in \mathcal{F}(\psi )\text{ and }V(F)\cap {\bigcup }_{x\in X}{N}_{R(G,\psi )}^d(x)=\varnothing \}|\le 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.

25 pages, 1 figure