Chromatic polynomials of connected graphs
type: Item
instance of: scholarly article
title: Chromatic polynomials of connected graphs
zbMATH Open document ID: 0535.05053
DOI: 10.1007/BF01193920
published in: Archiv der Mathematik
publication date: 1984-01-01T00:00:00Z
review text: We divide the family of connected graphs with \(n(\geq 3)\) vertices into 3 mutually disjoint subfamilies, namely, \({\mathcal F}_ 1\) consists of all connected graphs each of which has at least one cutpoint, \({\mathcal F}_ 2\) consists of all 2-connected graphs each of which has no subgraph homeomorphic to the complete graph \(K_ 4\) with 4 vertices, and \({\mathcal F}_ 3\) consists of all 2-connected graphs each of which has at least one subgraph homeomorphic to \(K_ 4\). Let G be a connected graph with \(n(\geq 3)\) vertices, and \(P(G,\lambda)=\lambda^ n-a_{n- 1}\lambda^{n-1}+...\pm a_ 1\lambda\) be its chromatic polynomial. Replacing \(\lambda\) in P(G,\(\lambda)\) by \(\omega +1\), we have \(P(G,\lambda)=Q(G,\omega)=\omega^ n+b_{n-1}\omega^{n-1}+...+b_ 1\omega.\) Here, we show that (1) \(G\in {\mathcal F}_ 1\) if and only if \(| b_ 1| =0\), (2) \(G\in {\mathcal F}_ 2\) if and only if \(| b_ 1| =1\), and (3) \(G\in {\mathcal F}_ 3\) if and only if \(| b_ 1| \geq 2\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 3849281
zbMATH Keywords: characterization of subclasses of graphs
zbMATH Keywords: chromatic polynomial
author: Chong-Yun Chao
author: Lianchang Zhao
MaRDI profile type: Publication
cites work: Q3313882
cites work: Q5528475
cites work: An introduction to chromatic polynomials
cites work: Cutpoints and the chromatic polynomial
full work available at URL: https://doi.org/10.1007/bf01193920
OpenAlex ID: W1985792286
description: scientific article; zbMATH DE number 3849281