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

Improvement of the numerical condition of chromaticity on complete tripartite graphs

设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)是色唯一图.

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.By comparing the number of the triangular subgraph and that of the quadrangular subgraph without chords,the chromatic uniqueness on the tripartite graph K(nk,n-v,n)was discussed.It was proved that K(n-k,n-v,n)is chromatically unique for n≥v^2(k-v/3)/4+vand k≥v≥2and that K(n-k,n-2,n)is chromatically unique for n≥k+2,k≥2.