|国家预印本平台
首页|Long cycles have the edge-Erd\H{o}s-P\'osa property

Long cycles have the edge-Erd\H{o}s-P\'osa property

Long cycles have the edge-Erd\H{o}s-P\'osa property

来源:Arxiv_logoArxiv
英文摘要

We prove that the set of long cycles has the edge-Erd\H{o}s-P\'osa property: for every fixed integer $\ell\ge 3$ and every $k\in\mathbb{N}$, every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ (long cycles) or an edge set $X$ of size $O(k^2\log k + \ell k)$ such that $G-X$ does not contain any long cycle. This answers a question of Birmel\'e, Bondy, and Reed (Combinatorica 27 (2007), 135--145).

Henning Bruhn、Felix Joos、Matthias Heinlein

数学

Henning Bruhn,Felix Joos,Matthias Heinlein.Long cycles have the edge-Erd\H{o}s-P\'osa property[EB/OL].(2016-07-07)[2025-08-02].https://arxiv.org/abs/1607.01903.点此复制

评论