关于完全三部图K(n-k,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.In this paper we prove that(1)For any non-negative integer k,if n>2(√)3k/3+k2,K(n-k,n,n+k) is chromatically unique.(2)If n≥9,K(n-3,n,n+3) is chromatically unique.%设G为简单图,P(G,λ)为G的色多项式,若对任意简单图H满足P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图.设K(m,n,r)表示完全三部图,证明了:(1)对任意非负整数k,若n>2(√)3k/3+k2,则K(n-k,n,n+k)是色唯一图.(2)若n≥9,则K(n-3,n,n+3)是色唯一图.