The chromatic uniqueness of certain complete \(t\)-partite graphs. (Q1420623): Difference between revisions

A graph \(G\) is called chromatically unique if any graph with the same chromatic polynomial as \(G\) is isomorphic to \(G\). This paper studies the chromatic uniqueness of complete \(t\)-partite graphs (\(t\geq3\)). Denote such a class of graphs by \({\mathcal L}_t\). The main result gives a sufficient condition for a graph \(G\in{\mathcal L}_t\), formulated in terms of the sizes of its partite sets, which guarantees that all graphs with the same chromatic polynomial as \(G\) belong to \({\mathcal L}_t\) as well. As a corollary, several classes of chromatically unique complete \(t\)-partite graphs are obtained. This also provides partial results about two problems of \textit{K.~M.~Koh} and \textit{K. L. Teo} [Graphs Comb. 6, 259--285 (1990; Zbl 0727.05023)].