三角化图的团划分数

在本文,我们证明了下述结果:(1)如果G=(V,E)是72个顶点的三角化图,则K(G)=α(G)≤cc(G)≤cp(G),cc(G)≤n-1,其中图G顶点独立数为α(G),它可在O(|V|+|E|)时间内求出;(2)如果G=(V,E)是n个顶点的特殊三角化图,V=S∪K,具有度序列为n-1≥d_1≥d_2≥…≥d_n,若对于S中任意顶点对x_i,x_j有|Adj(x_i)∩Adj(x_i)|≤1,则α(G)≤cp(G)≤α(G)+δ,其中,m=w(G)是图G的最大团的顶点个数。