On the chromatic equivalence class of graphs
type: Item
instance of: scholarly article
title: On the chromatic equivalence class of graphs
zbMATH Open document ID: 0918.05048
DOI: 10.1016/S0012-365X(97)81814-6
published in: Discrete Mathematics
publication date: 1999-08-10T00:00:00Z
review text: Let \(P(G, \lambda)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent if \(P(G,\lambda) = P(H,\lambda)\). The chromatic equivalence class of \(G\) consists of all graphs chromatically equivalent to \(G\). For example, the chromatic equivalence class of a tree consists of exactly all other trees of the same order. The join of two graphs \(G\) and \(H\) is obtained by taking a disjoint copy of each graph and adding edges from every vertex of \(G\) to every vertex of \(H\). The author determines the class of all graphs in the chromatic equivalence class of the join of \(m\) copies of paths each of length 3. He also gives two operations, which when applied to graphs in the chromatic equivalence class of \(G\), give all graphs with chromatic polynomial \(\lambda P(G,\lambda)\). A similar result is given for all graphs with chromatic polynomial \((\lambda -1) P(G,\lambda)\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1110101
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatic equivalence class
author: Gek L. Chia
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
cites work: On trees of polygons
cites work: Onq-trees
cites work: A note on chromatic uniqueness of graphs
cites work: Q3824333
cites work: On the chromatic equivalence class of a family of graphs
cites work: Q3990580
cites work: On graphs in which any pair of colour classes but one induces a tree
cites work: Q3682505
cites work: Q5572939
cites work: Q4044590
cites work: Q4031916
cites work: An introduction to chromatic polynomials
cites work: Q3832608
cites work: Q3243274
cites work: The chromaticity of complete bipartite graphs with at most one edge deleted
cites work: On the chromaticity of certain subgraphs of a q-tree
cites work: Chromaticity of two-trees
cites work: Cutpoints and the chromatic polynomial
description: scientific article; zbMATH DE number 1110101