On graphs in which any pair of colour classes but one induces a tree
type: Item
instance of: scholarly article
title: On graphs in which any pair of colour classes but one induces a tree
zbMATH Open document ID: 0874.05023
DOI: 10.1016/0012-365X(95)00331-P
published in: Discrete Mathematics
publication date: 1997-10-20T00:00:00Z
review text: For \(m\geq 3\), let \({\mathcal F}_m\) be the family of graphs \(G\) that possesses an independent set partition \(\{A_1,\ldots,A_m\}\) such that the subgraphs of \(G\) induced by \(A_i\cup A_j\) are trees except one, which is a forest having two components. In this paper it is shown that for each \(G\) of order \(n\) in \({\mathcal F}_m\), \(t(G)\leq f(n,m)=\frac{1}{3}(3n-2m) {{m-1} \choose {2}}-m+2\), where \(t(G)\) denotes the number of triangles in \(G\). Let \(\rho(G)=f(n,m)-t(G)\). The graphs in \({\mathcal F}_m\) with \(\rho(G)=0\) and the graphs in \({\mathcal F}_3\) with \(\rho(G)=1\) are characterized. By applying the first characterization, it is deduced that a graph \(G\) of order \(n\geq m\) is in \({\mathcal F}_m\) with \(\rho(G)=0\) iff its chromatic polynomial is given by \(\lambda(\lambda-1)\cdots(\lambda-m+3)(\lambda-m+2)^2(\lambda-m+1)^{n-m}\). By applying the second characterization it is shown that the graphs obtained from the wheels of even order by deleting two consecutive spokes are uniquely determined by their chromatic polynomials, which solves partially Problem 4 in \textit{K. M. Koh} and \textit{K. L. Teo} [Graphs Comb. 5, No. 3, 259-285 (1990; Zbl 0727.05023)].
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1021671
zbMATH Keywords: tree
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: wheel
zbMATH Keywords: chromatically unique graph
author: F. M. Dong
author: K. M. Koh
MaRDI profile type: Publication
cites work: Onq-trees
cites work: The chromaticity of wheels with a missing spoke
cites work: On rigid circuit graphs
cites work: On the structure and chromaticity of graphs in which any two colour classes induce a tree
cites work: Q5724802
cites work: Lower bounds on the number of triangles in a graph
cites work: The search for chromatically unique graphs
cites work: The search for chromatically unique graphs. II
cites work: The chromatic uniqueness of \(W_{10}\)
cites work: A note on the chromatic uniqueness of \(W_ 10\)
cites work: Q3819084
cites work: On the chromaticity of certain subgraphs of a q-tree
cites work: The chromaticity of wheels
full work available at URL: 0012-365x(95)00331-p
OpenAlex ID: W1989097746
Recommended article: On the chromatic uniqueness of the graph \(W(n,n-2,k)\)
Recommended article: Structures and chromaticity of extremal 3-colourable sparse graphs
Recommended article: Q4327762
Recommended article: The chromaticity of certain graphs with five triangles
Recommended article: On the join of graphs and chromatic uniqueness
Recommended article: Odd wheels in graphs
Recommended article: Q4346040
Recommended article: All wheels with two missing consecutive spokes are chromatically unique
Recommended article: A note on the chromatic uniqueness of \(W_ 10\)
Recommended article: The chromaticity of wheels with a missing spoke. II
description: scientific article; zbMATH DE number 1021671