Classes of chromatically equivalent graphs and polygon trees
type: Item
instance of: scholarly article
title: Classes of chromatically equivalent graphs and polygon trees
zbMATH Open document ID: 0813.05030
DOI: 10.1016/0012-365X(94)90033-7
published in: Discrete Mathematics
publication date: 1995-05-22T00:00:00Z
review text: If two graphs \(G\) and \(H\) have the same chromatic polynomial, i.e. \(P(G,\lambda)= P(H, \lambda)\), we say that \(G\) and \(H\) are chromatically equivalent. If \(P(G, \lambda)= P(H, \lambda)\) implies that \(H\) is isomorphic to \(G\), we say that \(G\) is chromatically unique. The author gives definitions of maximal classes of chromatically equivalent graphs and complete classes of chromatically equivalent graphs and investigates their properties. In particular, he studies graphs which contain no subgraph homeomorphic to \(K_ 4\) and shows that they are just generalized polygon trees. Next, he defines the notion of intercourse number of a generalized polygon tree and shows that this is an invariant of such a graph under chromatic equivalence. This result is very useful in the study of chromatically equivalent graphs. As a consequence, the author shows that \(\{\{C_{i_ 0},\dots, C_{i_ k}\}, k\{K_ 2\}\}\) is a complete class of chromatically equivalent graphs, which solves a problem raised by Whitehead Jr. in 1988.
reviewed by: Marek Kubale
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 681705
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatically equivalent
zbMATH Keywords: chromatically unique
zbMATH Keywords: polygon trees
zbMATH Keywords: intercourse number
zbMATH Keywords: chromatic equivalence
author: Shaoji Xu
MaRDI profile type: Publication
cites work: On trees of polygons
cites work: Onq-trees
cites work: On chromatic equivalence of graphs
cites work: Q3313882
cites work: The search for chromatically unique graphs
cites work: An introduction to chromatic polynomials
cites work: Chromaticity of two-trees
cites work: Chromatic polynomials of generalized trees
cites work: Cutpoints and the chromatic polynomial
cites work: The chromaticity of wheels
full work available at URL: 0012-365x(94)90033-7
OpenAlex ID: W1968267776
description: scientific article; zbMATH DE number 681705