A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs

AbstractLet P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H≅G. Koh, Teo and Chia conjectured that for any integers n and k with n⩾k+2⩾4, the complete tripartite graph K(n-k,n,n) is chromatically unique. Let K(n,m,r)-S denote the graph obtained by deleting all edges in S from the complete tripartite K(n,m,r). In this paper, we establish that for any positive integer n⩾m⩾r⩾2, the chromatic equivalence class of K(n,m,r) is contained in the family {K(x,y,z)-S|1⩽x⩽y⩽z,m⩽z⩽n,x+y+z=n+m+r,S⊂E(K(x,y,z)) and |S|=xy+xz+yz-nm-nr-mr}. By applying these results, we confirm this conjecture and show that K(n-k,n-1,n) is chromatically unique if n⩾2k and k⩾2