A Tighter Erdős‐Pósa Function for Long Cycles
A Tighter Erdős‐Pósa Function for Long Cycles
复制标题
更严格的长周期 Erdős-Pósa 函数
DOI：
10.1002/jgt.21776
复制
发表时间：
2012
影响因子：
0.9
通讯作者：
Audrey Herinckx
中科院分区：
文献类型：
--
作者：
Samuel Fiorini;Audrey Herinckx
我们证明存在一个二元函数 f，其中 f(k,ℓ)=O(ℓ·klogk)，使得对于每个自然 k 和 ℓ，每个图 G 至少有 k 个长度至少为 ℓ 的顶点不相交循环，或者一组至多 f(k,ℓ) 个顶点满足所有长度至少为 ℓ 的循环。这改进了 Birmelé 等人的结果。 (Combinatorica, 27 (2007), 135–145)，用 f(k,ℓ)=θ(ℓ·k2) 证明了相同的结果。
We prove that there exists a bivariate function f with f(k,ℓ)=O(ℓ·klogk) such that for every natural k and ℓ, every graph G has at least k vertex‐disjoint cycles of length at least ℓ or a set of at most f(k,ℓ) vertices that meets all cycles of length at least ℓ. This improves a result by Birmelé et al. (Combinatorica, 27 (2007), 135–145), who proved the same result with f(k,ℓ)=Θ(ℓ·k2) .