Some chromatic equivalence classes of complete multipartite graphs

Abstract

Let P(G, λ) be the chromatic polynomial of a graph G. For graphs G and H, if P{G, λ) = P(H, λ), then G and H are said to be chromatically equivalent. A graph G is chromatically unique if for any graph H, P(H,λ) = P(G, λ) implies H is isomorphic to G. Let [G] = {H|P(H,λ) = P(G, λ)} be the chromatic equivalence class determined by G. It is well known that a complete t-partite graph K(l,p₂,... ,pt) is chromatically unique if and only if pi ≤ 2 (2 ≤ t ≤ t). However, the chromatic equivalence class of K(l,p,q) for q ≥ 3 is only known for K(l,l,q), K(1,2,4), K(l,3,4) and K(l,q, q). In this paper, we completely determined the chromatic equivalence class of K(l,p- l,p) for p ≥ 3 which partially answered the question What is the chromatic equivalence class for the graph K(l,p,q), where 2 ≤ P < q ? raised in [Discrete Maths. 309 (2008), 134-143]. We also completely determined the chromatic equivalence class of K(l,p.....p). © 2017 Utilitas Mathematica Publishing Inc.. All rights reserved.