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

摘要：

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

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

所属期刊栏目：16

分类号：O157.6(代数、数论、组合理论)

在线出版日期：2007-10-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：61-63