完全3部图K(n-k,n-3,n)色唯一性的证明（英文）

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图.这里,通过比较图的三角形子图和无弦四边形的个数,完全解决了一类完全三部图K(n-k,n-3,n)的色唯一性问题,证明了,若n≥k+2≥5,则完全三部图K(n-k,n-3,n)是色唯一图.

完全三部图色唯一性数值条件的改进

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G■H),则称图G是色唯一图.这里通过比较图的三角形子图和无弦四边形子图的个数,讨论了完全三部图K(n-k,n-v,n)的色唯一性.证明了若n≥v^2(k-v/3)/4+v,k≥v≥2,则完全三部图K(n-k,n-v,n)是色唯一图;若n≥k+2,k≥2,则完全三部图K(n-k,n-2,n)是色唯一图.