The chromatic uniqueness of certain complete \(t\)-partite graphs.
type: Item
instance of: scholarly article
title: The chromatic uniqueness of certain complete \(t\)-partite graphs.
zbMATH Open document ID: 1036.05024
author: Hui Wen Zou
published in: Discrete Mathematics
publication date: 2004-02-02T00:00:00Z
review text: 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)].
reviewed by: Tomáš Dvořák
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2035889
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatically unique graph
MaRDI profile type: Publication
full work available at URL: j.disc.2003.06.014
OpenAlex ID: W2033759548
cites work: A new 5‐arc‐transitive cubic graph
cites work: Q5422499
cites work: On maximally saturated graphs
cites work: On chromatic equivalence of graphs
cites work: Q3990580
cites work: The search for chromatically unique graphs
cites work: The search for chromatically unique graphs. II
cites work: The chromaticity of the complete \(t\)-partite graph \(K(1,p_2,\cdots,p_t)\)
cites work: The chromaticity of complete bipartite graphs with at most one edge deleted
cites work: Q4502934
DOI: 10.1016/J.DISC.2003.06.014
description: scientific article; zbMATH DE number 2035889