完全三部图K(n,n,n+k)的色性

摘要

Let P(G,λ)denote the chromatic polynomial of a simple graph G.Then G is said to be chromatically unique if for any simple graph H,P(H,λ)=P(G,λ)implies that H is isomorphic to G.Let K(m,n,r)denote a complete tripartite graph.We prove that (1) for any non-negative integerk,if n＞(k+k2)/3,then K(n,n,n+k)is chromatically unique;(2)if n≤4,then K(n,n,n+4)is chromatically unique.%设G为简单图,P(G,λ)为G的色多项式.若对任意简单图H满足P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图.设K(m,n,r)表示完全三部图.证明了(1)对任意非负整数k,若n≥k+k2/3,则K(n,n,n+k)是色唯一图;(2)若n≥4,则K(n,n,n+4)是色唯一图.