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

Let P (G, lambda) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, lambda) = P(G, lambda) implies H congruent to G. Koh, Teo and Chia conjectured that for any integers n and k with n greater than or equal to k + 2 greater than or equal to 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 greater than or equal to m greater than or equal to r greater than or equal to 2, the chromatic equivalence class of K (n, m, r) is contained in the family {K (x, y, z) - S\1 less than or equal to x less than or equal to y less than or equal to z, m less than or equal to z less than or equal to n, x + y + z = n + m + r, S subset of 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 greater than or equal to 2k and k greater than or equal to 2. (C) 2004 Elsevier B.V. All rights reserved.