On the chromaticity of complete multipartite graphs with certain edges added

• Published in: Discrete Mathematics
• Main Author: Lau G.C.; Peng Y.H.
• Format: Article
• Language: English
• Published: 2009
• Online Access: https://www.scopus.com/inward/record.uri?eid=2-s2.0-67349096082&doi=10.1016%2fj.disc.2008.12.008&partnerID=40&md5=7a46f9900f08845ace27be6128d38575

Let 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 is isomorphic to G. For integers k ≥ 0, t ≥ 2, denote by K ((t - 1) × p, p + k) the complete t-partite graph that has t - 1 partite sets of size p and one partite set of size p + k. Let K (s, t, p, k) be the set of graphs obtained from K ((t - 1) × p, p + k) by adding a set S of s edges to the partite set of size p + k such that 〈 S 〉 is bipartite. If s = 1, denote the only graph in K (s, t, p, k) by K+ ((t - 1) × p, p + k). In this paper, we shall prove that for k = 0, 1 and p + k ≥ s + 2, each graph G ∈ K (s, t, p, k) is chromatically unique if and only if 〈 S 〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K+ ((t - 1) × p, p + k) is chromatically unique for k = 0, 1 and p + k ≥ 3. © 2008 Elsevier B.V. All rights reserved.