论文部分内容阅读
图被称为K1,n-free图,如果它不含有导出子图K1,n。设G是一个具有顶点集V(G)的图,并设g和f是两个定义在V(G)的函数,使得g(x)≤f(x)对所有V(G)中的点x都成立。设a=max|g(x)|x∈V(G)|,b=min|f(x)|x∈V(G)|,并有b,a≥2,n≥b/(a-1)+1(如果存在点v∈V(G)使得f(v)≡1(mod 2),假定b≥n-1)。证明了:每个连通的使得∑x∈V(G)f(x)为偶数的K1,n-free图G有(g,f)-因子,如果它的最小度至少是((n-1)(a+1)