Chromaticity of series-parallel graphs
type: Item
instance of: scholarly article
title: Chromaticity of series-parallel graphs
zbMATH Open document ID: 0856.05035
DOI: 10.1016/0012-365X(94)00355-M
author: Chung-Piaw Teo
author: K. M. Koh
published in: Discrete Mathematics
publication date: 1996-07-18T00:00:00Z
review text: If \(P(G, \lambda)\) denotes the chromatic polynomial of a graph \(G\), two graphs \(G\) and \(H\) are said to be \(\chi\)-equivalent, written \(G \sim H\), if \(P(G, \lambda) = P (H, \lambda)\). Any equivalence class induced by \(\sim\) is called a \(\chi\)-equivalence class. A \(k\)-gon tree is obtained by edge-gluing a set of cycles each of order \(k\) successively. A graph is called a generalised polygon tree if it is a subdivision of a \(k\)-gon tree. Alternatively, a generalised polygon tree can be viewed as a 2-connected simple series-parallel graph (sp graph). In this paper some new chromatic invariants for sp graphs are introduced and it is proved that the class of polygon trees is a \(\chi\)-equivalence class. A class of sp graphs, called \(\Theta_k\)-gons, is shown to be closed under \(\chi\)-equivalence and some classes of \(\Theta_k\)-gons are identified to possess the same property; one of them is the class of \(k\)-gon trees.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 906912
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: generalised polygon tree
zbMATH Keywords: series-parallel graph
zbMATH Keywords: chromatic invariants
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: On trees of polygons
cites work: On chromatic equivalence of graphs
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Topology of series-parallel networks
cites work: The search for chromatically unique graphs
cites work: Q4486183
cites work: Chromatic uniqueness of the generalized \(\Theta\)-graph
cites work: An introduction to chromatic polynomials
cites work: Q3819084
cites work: Chromatic polynomials, polygon trees, and outerplanar graphs
cites work: Chromatic polynomials of generalized trees
cites work: Classes of chromatically equivalent graphs and polygon trees
cites work: The chromaticity of \(s\)-bridge graphs and related graphs
full work available at URL: 0012-365x(94)00355-m
OpenAlex ID: W1970753020
description: scientific article; zbMATH DE number 906912