一类完全三部图的色唯一性  

Chromatic Uniqueness of a Kind of Complete Tripartite Graphs

作　　者：苏克义 陈祥恩[2] 

机构地区：[1]宁夏银川市第六中学,宁夏银川750011 [2]西北师范大学数学与信息科学学院,甘肃兰州730070

出　　处：《数学的实践与认识》2011年第2期163-171,共9页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10771091);甘肃省教育厅科研项目(0501-02)

摘　　要：用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k^2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.Let P（G,λ） denote the chromatic polynomial of a simple graph G.Graph G issaid to be chromatically unique if for any simple graph H,P（H,λ） = P（G,λ） implies that His isomorphic to G（or simply H≌G）.The following result has been proved in this paper：fornonnegative integers n,k,△,where k≥0,△∈{4,5},if n≥1/3k2＋ 1/3△2-1/3k△-1/3k-1/3△＋4/3,then the complete tripartite graph K（n,n ＋△,n ＋ k） is chromatically unique.Furthermore,we present a conjecture.

关 键 词：完全三部图 色多项式 色唯一图 色划分 

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