关于连通度的无三圈图的划分

摘要

Kühn and Osthus proved that for every positive integer l,there exists an integer k(l) ≤ 216 l2,such that the vertex set of every k(1)-connected graphs G can be partitioned into subsets S and T with the properties that both G[S] and G[T] are l-connected and every vertex in S has at least l neighbors in T.In this paper,we consider the upper bound of k(l) on triangle-free graphs.After showing that every triangle-free graph of average degree at least 81/3 has an l-connected subgraph,we prove that k(1) ≤ 216 · 3-3 · l2 on triangle-free graphs.%Kühn和Osthus证明了对每个正整数l,都存在一个整数k(l)≤216 l2,使得每个k(l)—连通图G的顶点集都可以划分成两个子集S,T满足G[S],G[T]都是l—连通的,且S中的每个点在T中都有l个邻点.本文主要考虑无三圈图的划分问题,主要关注连通度k(l)的上界.通过证明每个平均度至少为8l/3的无三圈图都存在一个l-连图子图,我们证明了对无三圈图,k(l)≤216·3-3 l2.