Chromatic Uniqueness of Certain Complete \(4\)-partite Graphs

Abstract

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\) is isomorphic to \(G\). It is known that a complete tripartite graph \(K(a,b,c)\) with \(c \geq b \geq a \geq 2\) is chromatically unique if \(c – a \leq 3\). In this paper, we proved that a complete \(4\)-partite graph \(K(a,b,c,d)\) with \(d \geq c \geq b \geq a \geq 2\) is also chromatically unique if \(d – a \leq 3\).