关于完全t部图K(n_1,n_2,…,n_t)的色唯一性

On Chromaticity of Complete t-partite Graphs

设P(G,λ)是图G的色多项式,如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称G是色唯一图。这里通过比较图的特征子图的个数,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,1≤i,j≤t且min{n1,n2,…,nt}充分大,K(n1,n2,…,nt)是否为色唯一图?)。证明了,若|ni-nj|≤2且∑ti=1ni>t22+t t-1,则K(n1,n2,…,nt)是色唯一图;若ai=0或k,∑ti=1n+ai>t28k2+|t2k|t-1,则K(n+a1,n+a2,…,n+at)是色唯一图。其条件比文献[4]中的条件较好一些。

Let P（G,λ）be the chromatic polynomial of graph G.A graph G is chromatically unique if any graph H,P（λ）=P（G,λ） implies H≌G.Comparing the numbers of the characteristic subgraphs of the graphs,we discuss the problem （for each t≥2,is the graph K（n1,n2,…,nt） chromatically unique if ｜ni-nj｜≤2 for all i,j=1,2,…,t and if min{n1,n2,…,nt} is sufficiently large？） brought forward by Koh and Teo in [1].We prove that K（n1,n2,…,nt） is chromatically unique for ｜ni-nj｜≤2 and t↑∑↑i=1 ni〉t^2/2＋t√t-1,Let 0i=0 or k,and we prove that K（n＋α1,n＋α2,…,n＋αt） is chromatically unique for t↑∑↑i=1 ni〉t^2k^2/8＋｜tk｜/2√t-1,The condition is better than that in [4].