一类完全三部图K(m,n,r)的色唯一性的判定  

Judgement on the Chromatic Uniqueness of A Families of Complete Tripartite Graphs K(m,n,r)

作　　者：林永[1] 邹辉文[1] 

机构地区：[1]东华理工学院计算科学与信息管理系

出　　处：《江西科学》2006年第2期166-169,190,共5页Jiangxi Science

基　　金：江西省教育厅科技项目(2002-01)

摘　　要：设G是简单图,用P(G,λ)表示图G的色多项式,若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图。令K(m,n,r)表示完全三部图,证明了(1)设m≤n≤r,0≤r-m≤4,若m≥2,则除去K(2,2,6)、K(2,3,6)、K(3,3,7)、K(3,4,7)外,K(m,n,r)是色唯一图。(2)若n≥4,0≤k≤2,则K(n-k,n,n+k)是色唯一图。Let G be a simple graph and P（G,A） denote the chromatic polynomial of G. A graph G is said to be chromatically unique if for any graph H, P （ H, λ ） = P （ G, λ ）, implies that H is isomorphic to G. Let K（ m, n, r） denote a complete tripartite graph, this paper proved that （ 1 ） If m ≤n ≤r,0≤ r - m ≤4 and m ≥2, the graphs K（ m, n, r） is chromatically unique except for k（ 2,2,6） ,K（ 2,3,6） , K（3,3,7） ,K（3,4,7）. （2）If n≥4,0≤k≤2 ,the graphs K（n -k,n,n ＋k） is chromatically unique.

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

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