摘要
设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.
出处
《江西科学》
2006年第2期166-169,190,共5页
Jiangxi Science
基金
江西省教育厅科技项目(2002-01)
关键词
完全三部图
色唯一图
色划分
Complete tripartite graph, Chromatically unique graph, Partition into colour classes
