Chromatic equivalence classes of certain generalized polygon trees
type: Item
instance of: scholarly article
title: Chromatic equivalence classes of certain generalized polygon trees
zbMATH Open document ID: 0883.05058
DOI: 10.1016/S0012-365X(96)00273-7
author: Bernhard Rupp
published in: Discrete Mathematics
publication date: 1998-03-16T00:00:00Z
review text: The graphs considered in this paper are generalized polygon trees with three interior regions, which can be defined non-recursively as follows: the graph \(G^s_t(a,b;c,d)\) has at most 4 vertices \(u\), \(v\), \(w\), \(x\), the are two disjoint paths of lengths \(d\geq 2\) and \(c\geq d\) joining \(u\) and \(v\), and of lengths \(b\geq 2\) and \(a\geq b\) joining \(w\) and \(x\), one of length \(s\geq 0\) joining \(u\) and \(w\) (if \(s=0\) then \(u=w\)) and one of length \(t\geq 0\) joining \(v\) and \(x\) (if \(t=0\) then \(v=x\)). Let \(C_r(a,b;c,d)\) be the family \(\{G^s_t(a,b; c,d)\mid r=s+t, s\geq 0, t\geq 0\}\). Two graphs are called chromatically equivalent if they have the same chromatic polynomial. Several referenced papers give necessary and sufficient conditions for \(C_r(a,b; c,d)\) to be a chromatic equivalence class for fixed values of some of the parameters \(r\), \(a\), \(b\), \(c\), \(d\), and in [\((*)\) \textit{Y.-H. Peng}, Another family of chromatically unique graphs, Graphs Comb. 11, No. 3, 285-295 (1995; Zbl 0836.05028)] it is shown that \(G^0_1(a,b; c,d)\) is in a chromatic class by itself if \(\min\{a,b,c,d\}\geq 4\). The paper under review presents several sufficient conditions for \(C_r(a,b; c,d)\) to be a chromatic equivalence class, of which the following two are proved: \(\min\{a,b, c,d\}\geq r+3\geq 4\) (from which the result of \((*)\) is derived as a corollary) and \(r\geq a\geq b+3\geq c+ 6\geq d+9\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1061987
zbMATH Keywords: generalized polygon trees
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatic equivalence class
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Q3818315
cites work: Chromatic classes of certain 2-connected \((n,n+2)\)-graphs. II
cites work: The chromaticity of complete bipartite graphs with at most one edge deleted
cites work: Another family of chromatically unique graphs
cites work: Q3728929
cites work: An introduction to chromatic polynomials
cites work: Q4000770
cites work: Classes of chromatically equivalent graphs and polygon trees
cites work: The chromaticity of \(s\)-bridge graphs and related graphs
cites work: Q5790850
full work available at URL: s0012-365x(96)00273-7
OpenAlex ID: W4212796423
Recommended article: Q3501872
Recommended article: Chromatic equivalence classes of certain generalized polygon trees. III
Recommended article: Q3411676
Recommended article: Q5466079
Recommended article: Chromatic equivalence classes of certain cycles with edges
Recommended article: Chromaticity of series-parallel graphs
Recommended article: Classes of chromatically equivalent graphs and polygon trees
Recommended article: On the chromatic equivalence class of graphs
Recommended article: Q3818334
Recommended article: Generalized trees and their applications
description: scientific article; zbMATH DE number 1061987