设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图.这里通过比较图的三角形子图和无弦四边形子图的个数,讨论了完全三部图K(n—k,7—v,n)的色唯一性.证明了若n≥v2(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 G is 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(n—k,n—v,n) was discussed.It was proved that K(n—k,n—v,n) is chromatically unique for n≥v2 (k—v/3)/4+v and k≥v≥2 and that K(n—k,n—2,n) is chromatically unique for n≥k+2,k≥2.
展开▼
