On the Chromaticity of the Complete Tripartite Graph K(n-k,n,n)
Zou Hui · 1999
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 the complete tripartite graph. We prove that (1) If nk+k 2/3, then the graph K(n-k,n,n) is chromatically unique. (2) If n≥8, then K(n-4,n,n) is chromatically unique.