完全t部图的色唯一性

作者：徐利民; 杨志林

来源：淮南职业技术学院学报, 2011, (06): 79-81.

• 色唯一图
• 色划分数
• 完全t部图
• 色等价

设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;这里通过比较t部图的t 1色类的划分数,证明了若min1≤i≤t{n ai}≥1/2(a12 a22 … at2)-1/2t(a1 a2 … at2) 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)是色唯一的。

• 单位
  淮南职业技术学院; 合肥工业大学