图中K个边不交的圈的存在性问题

The Existence of Edge-disjoint Cycles in Graphs

记h(k)是使得满足ε=ν+h(k)的有限的无向图G包含k个边不交的圈的最小整数,P.Erds和L.Pósa证明了h(2)=4且对于任意正整数k≥1,存在充分小的正常数c1和充分大的正常数c2,使得c1klog2k≤h(k)≤c2klog2k。现把充分大的正常数c2的界缩紧到2.1<c2≤3,特别当c2为整数时,则c2=3,并比较简洁地证明了h(3)≤10和当图G是平面图时,对于任意正整数k≥2,h(k)=4k-5。

For a finite and undirected graph, we use symbols to denote the smallest integer. P. Erdos and L. Pósa proved where h（2）=4 and every positive integer k≥ 1, there exists a sufficiently small positive constant cl and a sufficiently large positive constant c2, satisfying clklog2 k≤h（k）≤c2klog2 k. In this paper, the limit of the sufficiently large positive constant c2 is compressed to 2.1〈c2≤ 3. Especially when c2 is an integer, then c2=3. It proves succinctly and innovatively that when h（3）≤ 10 and the graph is a planar graph, for any positive k≥2,h （k）=4k-5.