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

On the chromaticity of complete t-partite graph K(n-k,n-2,n,…,n)

作　　者：徐利民[1,2] 杨志林[1] 

机构地区：[1]合肥工业大学数学学院,安徽合肥230009 [2]淮南职业技术学院基础部,安徽淮南232001

出　　处：《合肥工业大学学报（自然科学版）》2013年第9期1148-1152,共5页Journal of Hefei University of Technology：Natural Science

基　　金：淮南职业技术学院科研资助项目(HKJ10-6)

摘　　要：文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。The chromaticity of complete t-partite graph K（n-k,n-2,n,…,n） is introduced. Let P（G, 2） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, A）=P（G, /l） implies HG. By comparing the chromatic number of partition into t＋1-color classes of the t-partite graph and the number of the triangular subgraph of graphs, it is proved that K（n-k,n-2,n,…,n） is chromatically unique if n〉[（k＋1）2/4]＋1 and k〉2.

关 键 词：色唯一图 色划分数 完全t部图 三角形子图 

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