完全t部图K(n-k,n,…,n)的色唯一性

Chromatic uniqueness of complete t-partite graphs K(n-k,n,…,n)

设P(G,λ)是图G的色多项式.如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.通过比较图的特征子图的个数,讨论了由文献[Koh K M,Teo K L.The search for chromatically unique graphs.Graphs and Combinatorics,1999,6:259-285]中提出的猜想(若n≥k+2,则完全三部图K(n-k,n,n)是色唯一图);推广了文献[Liu Ru-yin,Zhao Hai-xing,Ye Cheng-fu.A complete solution to a conjecture on chromatic unique of complete tripartite graphs.Discrete Mathematics,2004,289:175-179]中的结果(若n≥k+2≥4,则K(n-k,n,n)是色唯一图;若n≥2k≥4,则K(n-k,n-1,n)是色唯一图);证明了若n≥k+2≥4,则K(n-k,n,…,n)是色唯一图,若n≥k+2≥4,则K(n-k,n-1,n,…,n)是色唯一图.

Let P（G,λ） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（G,λ）=P（H,λ） implies H≌ G. By comparing the numbers of the characteristic subgraph of graphs, the conjecture （For n≥k＋2, the graph K（n-k,n,n） is chromatically unique） brought forward by Koh and Teo in Ref. [Koh K M, Teo K L. The search for chromatically unique graphs. Graphs and Combinatorics, 1999,6： 259-285] was discussed. The result（For n≥k＋2≥4, the graph K（n-k,n,n） is chromatically unique; for n≥2k≥4, the graph K （n- k, n- 1, n） is chromatically unique） given in Ref. [Liu Ru-yin, Zhao Hai-xing, Ye Cheng-fu. A complete solution to a conjecture on chromatic unique of complete tripartite graphs. Discrete Mathematics, 2004, 289. 175 179] was generalized. It was proved that K（n-k,n,... ,n） is chromatically unique for unique for n≥k＋2≥4.