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

Proof of chromaticity of the complete tripartite graphs 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)是色唯一图.

Let P(G,λ)be the chromatic polynomial of a graph G.A graph Gis chromatically unique if for any graph H,P(H,λ)=P(G,λ)implies G≌H.Here,by comparing the number of the triangular subgraphs and the number of the quadrangular subgraphs without chords,the chromatic uniqueness problem of the complete tripartite graphs K(n-k,n-3,n)was completely solved.It was proved that K(n-k,n-3,n)is chromatically unique if n≥k+2≥5.