完全t部图的色唯一性

摘要

设P(G.λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G.λ)=P(H.λ))的图H都与图G同构(G≌H),则称图G是色唯一图；这里通过比较t部图的t+1色类的划分数,证明了若mint≦i≦t(n+a,}≥1/2(a12+a22+…+2t2)-1/2t(a1-a2十…+at)2+1,则完全t部图K(n+a1,n+a2,…,n十at)是色唯一图；若n≥t-1/2t(k2+v2)+1/tkv+v+1,v≥0,k≥-v,则完全t部图K (n-v,n,n+k,n,…,n)是色唯一的.