关于完全t部图的色唯一性  

On the Chromaticity of Complete t-partite Graphs

作　　者：徐利民[1] 

机构地区：[1]淮南职业技术学院,安徽淮南232001

出　　处：《运筹与管理》2007年第4期61-63,共3页Operations Research and Management Science

摘　　要：设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t+1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n+a1,n+a2,…,nt+at,n-1}≥(T+1)/2,则K(n+a1,n+a2,…,n+at)是色唯一图(其中ai是实数,n+ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8+1,则K(n1,n2,…,nt)是色唯一图。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 H≌G. In this paper, comparing the partition numbers of t＋1 color classes 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？） that was brought forward by Koh and Teo in. We improve the result given in. We prove that K（n-a1, n＋a2 ,…, n＋at,） is chromatically unique for ∑1≤i≤tai^2=T.and min{n＋a1,n＋a2,….nt＋at,n-1}≥（T＋1）/2, where ai is a real and n＋ai is a positive integer. By applying these results, we prove that K（n＋a1.n＋a2,….n＋a,）is chromatically unique for│ni-nj│≤k（i.j=1,2.…,t）.min{n1.n2,…,nt}≥tk^2/8＋1.

关 键 词：运筹学 色唯一图 色划分数 完全t部图 色等价 

分 类 号：O157.6[理学—数学]