The chromatic uniqueness of certain complete \(t\)-partite graphs. (Q1420623)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The chromatic uniqueness of certain complete \(t\)-partite graphs.
scientific article

    Statements

    The chromatic uniqueness of certain complete \(t\)-partite graphs. (English)
    0 references
    0 references
    2 February 2004
    0 references
    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)].
    0 references
    0 references
    chromatic polynomial
    0 references
    chromatically unique graph
    0 references
    0 references