Chromaticity of some families of dense graphs
type: Item
instance of: scholarly article
title: Chromaticity of some families of dense graphs
zbMATH Open document ID: 1010.05024
DOI: 10.1016/S0012-365X(02)00355-2
author: K. L. Teo
author: M. D. Hendy
author: F. M. Dong
author: C. H. C. Little
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: The chromatic polynomial of a graph \(G\) is denoted by \(P(G,\lambda).\) Two graphs \(G\) and \(H\) are said to be chromatically equivalent, written \(G\sim H,\) if \(P( G,\lambda) =P( H,\lambda) \). The relation \(\sim \) is obviously an equivalence relation. This paper studies the problem of determining the chromatic equivalence classes of graphs whose complements have isolated vertices, paths or cycles as their components. A corollary of one of the results is that the conjecture of \textit{R.-Y. Liu} [Discrete Math. 172, 85-92 (1997; Zbl 0878.05030)] is true, i.e. the complement of \(P_{n}\) is chromatically unique for every even \(n\neq 4\).
reviewed by: Marietjie Frick
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1839037
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatically equivalent
zbMATH Keywords: chromatically unique
zbMATH Keywords: adjoint polynomial
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1839037