The chromatic uniqueness of certain complete t-partite graphs

AbstractLet G be a simple graph and P(G,λ) denote the chromatic polynomial of 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. A class L of graphs is called a class of chromatically normal graphs if, for any Y,G∈L, P(Y,λ)=P(G,λ) implies that Y is isomorphic to G. Let K(n1,n2,…,nt) denote a complete t-partite graph and Lt={K(n1,n2,…,nt)|0<n1⩽n2⩽⋯⩽nt}. The main results of the paper are as follows.Let G=K(n1,n2,…,nt)∈Lt,t⩾3,Q(G)={Y|P(Y,λ)=P(G,λ)} and at=∑1⩽i<j⩽t(ni−nj)2/(2t)1/2. If (∗)∑i=1tni>tat2+2t(t−1)at,then Q(G)⊆Lt. Furthermore, if Lt is also a class of chromatically normal graphs, then G is chromatically unique. In particular, if G satisfies the condition (*) and one of the following conditions:(i)n1=n2=⋯=nt,(ii)n1<n2<⋯