Chromaticity of a family of \(K_{4}\)-homeomorphs
type: Item
instance of: scholarly article
title: Chromaticity of a family of \(K_{4}\)-homeomorphs
zbMATH Open document ID: 1027.05039
DOI: 10.1016/S0012-365X(02)00268-6
author: Yan-ling Peng
author: Ru Ying Liu
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: A graph is chromatically unique if it is uniquely determined up to isomorphism by its chromatic polynomial. A \(K_4\)-homeomorph is a subdivision of the complete graph \(K_4\), i.e. a graph consisting of six paths, also called \(*\)-paths, joining four vertices of degree three. It is well known that almost all \(K_4\)-homeomorphs are chromatically unique [\textit{W. Li}, Ars Comb. 23, 13-35 (1987; Zbl 0644.05020)]. The paper under review studies the family of \(K_4\)-homeomorphs having the property that all but two adjacent \(*\)-paths have length more than one. The authors prove a necessary and sufficient condition, formulated in terms of lengths of \(*\)-paths, for the graphs in this family to be chromatically unique. This complements a result of \textit{S.~Xu} [Discrete Math. 117, 293-297 (1993; Zbl 0781.05022)] who obtained a similar characterization for the family of \(K_4\)-homeomorphs with two nonadjacent \(*\)-paths of length one.
reviewed by: Tomáš Dvořák
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1839028
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatic uniqueness
zbMATH Keywords: \(K_4\)-homeomorph
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1839028