Long Cycles have the Edge-Erdos-Pósa Property
Long Cycles have the Edge-Erdos-Pósa Property
复制标题
长周期具有边缘-鄂尔多斯-波萨性质
DOI：
10.1007/s00493-017-3669-x
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
Bruhn H
中科院分区：
文献类型：
--
作者：
Bruhn H
我们证明长环集合具有边Erdős-Pósa性质：对于每个固定整数ℓ≥3且每个k∈ℕ，每个图G要么包含长度至少为ℓ（长环）的边不相交环，要么包含大小为O（k2logk+kℓ）的边集X，使得G—X不包含任何长环。这回答了 Birmelé、Bondy 和 Reed 的问题 (Combinatorica27(2007), 135-145)。
We prove that the set of long cycles has the edge-Erdős-Pósa property: for every fixed integerℓ≥ 3 and everyk∈ ℕ, every graphGeither containskedge-disjoint cycles of length at leastℓ(long cycles) or an edge setXof sizeO(k2logk+kℓ) such thatG—Xdoes not contain any long cycle. This answers a question of Birmelé, Bondy, and Reed (Combinatorica27(2007), 135-145).