Abstract :
Let 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) | 0tat2+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
Keywords :
Chromatically normal graphs , Complete t-partite graph , Chromatically unique graph , Partition into color classes
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics