Chromatic uniqueness in a family of 2-connected graphs
type: Item
instance of: scholarly article
title: Chromatic uniqueness in a family of 2-connected graphs
zbMATH Open document ID: 0880.05039
DOI: 10.1016/S0012-365X(96)00039-8
author: Halina Bielak
published in: Discrete Mathematics
publication date: 1998-01-14T00:00:00Z
review text: Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are said to be chromatically equivalent if \(P(G,\lambda)= P(H,\lambda)\). A graph \(G\) is said to be chromatically unique, if there exists no graph \(H\), which is not isomorphic with \(G\), but \(G\) and \(H\) are chromatically equivalent. For integers \(n\geq 4\) and \(k\geq 1\), the graph \(F_{n,k}\) is defined as follows. Let \(H_n= P_{n-1}+ K_1\) be the join of a path \(P_{n-1}\) on \(n-1\) vertices with a vertex. Then \(H_n\) has exactly two vertices, say \(x\) and \(y\), each of degree 2. The graph \(F_{n,k}\) is obtained from \(H_n\) by adjoining \(k\) new vertices \(u_1,u_2,\dots,u_k\) and adding \(2k\) edges joining them to \(x\) and \(y\). The author proves that, for any odd integer \(n\geq 5\) and any integer \(k\geq 1\), \(F_{n,k}\) is chromatically unique. This gives a partial solution to Problem 5 given in \textit{K. M. Koh} and \textit{K. L. Teo} [The search for chromatically unique graphs, Graphs Comb. 6, No. 3, 259-285 (1990; Zbl 0727.05023)]. Reviewer's remark: K. L. Teo was misprinted as C. P. Teo in this paper.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1019050
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: chromatically equivalent
zbMATH Keywords: chromatically unique
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: Chromatically unique graphs
cites work: The search for chromatically unique graphs
cites work: Parallel concepts in graph theory
cites work: An introduction to chromatic polynomials
Recommended article: Another family of chromatically unique graphs
Recommended article: A note on the chromaticity of some 2-connected \((n,n+3)\)-graphs
Recommended article: Q3682504
Recommended article: Q5202203
Recommended article: Q3722526
Recommended article: Q4368025
Recommended article: Q3366862
Recommended article: The chromaticity of complete bipartite graphs with at most one edge deleted
Recommended article: Classes of chromatically unique graphs
Recommended article: Q4315777
description: scientific article; zbMATH DE number 1019050