On the Chromaticity of Complete t-partite Graphs
Author(s): XU Li-min
Pages: 61-63
Year: 2007 Issue: 4
Journal: OPERATIONS RESEARCH AND MANAGEMENT SCIENCE
Keyword: 运筹学; 色唯一图; 色划分数; 完全t部图; 色等价;
Abstract: 设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)是色唯一图.
Pages: 61-63
Year: 2007 Issue: 4
Journal: OPERATIONS RESEARCH AND MANAGEMENT SCIENCE
Keyword: 运筹学; 色唯一图; 色划分数; 完全t部图; 色等价;
Abstract: 设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)是色唯一图.
Related Articles