On \(\sigma\)-polynomials and a class of chromatically unique graphs
type: Item
instance of: scholarly article
title: On \(\sigma\)-polynomials and a class of chromatically unique graphs
zbMATH Open document ID: 0774.05039
DOI: 10.1016/0012-365X(93)90485-C
author: Qing Yan Du
published in: Discrete Mathematics
publication date: 1993-06-20T00:00:00Z
review text: The \(\sigma\)-polynomial of a graph was defined in \((*)\) \textit{R. R. Korfhage} [\(\sigma\)-polynomials and graph colouring, J. Comb. Theory, Ser. B 24, No. 2, 137-153 (1978)]. For a graph \(G\) with \(n\) vertices and chromatic number \(\chi(G)\), let \(k=n-\chi(G)\). If \(P(G,\lambda)\), the chromatic polynomial of \(G\), is \(\sum^ k_{i=0}a_ i\lambda(\lambda- 1)\cdots(\lambda-n+i+1)\), then \(\sigma(G)=\sum^ k_{i=0}a_ i\sigma^{k-i}\). It is known that \(a_ i>0\) for \(0\leq i\leq k\), \(a_ 0=1\) and \(a_ 1\) is the number of nonadjacent pairs of vertices of \(G\). It was shown in \((*)\) that \(a_ i\leq{a_ 1\choose i}\) for \(2\leq i\leq k\) and in \textit{S.-J. Xu} [On \(\sigma\)-polynomials, Discrete Math. 69, No. 2, 189-194 (1988; Zbl 0658.05025)] that if \(\sigma^ 2+a\sigma+b\) is a \(\sigma\)-polynomial, then \(b\leq a^ 2/4\). In the paper under review, these results, together with a necessary and sufficient condition for the inequalities in \((*)\) to be sharp for at least one value of \(i\), are obtained as special cases of an upper bound for \(a_ i\) in terms of elementary symmetric functions. A graph \(G\) is called chromatically unique if only isomorphic copies of \(G\) have the same chromatic polynomial as \(G\), and a 2-parameter family of chromatically unique graphs is presented.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05E05
zbMATH DE Number: 205597
zbMATH Keywords: chromatically unique graphs
zbMATH Keywords: chromatic number
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: upper bound
zbMATH Keywords: symmetric functions
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q4770409
cites work: \(\sigma\)-polynomials and graph coloring
cites work: Q3320409
cites work: An introduction to chromatic polynomials
cites work: Characterization of quadratic and cubic \(\sigma\)-polynomials
cites work: On \(\sigma\)-polynomials
Recommended article: On ?-equivalence and ?-equivalence of graphs
Recommended article: Classification of chromatically unique graphs having quadratic σ‐polynomials
Recommended article: On \(\sigma\)-polynomials
Recommended article: \(\sigma\)-polynomials and graph coloring
Recommended article: On graphs having \(\sigma\)-polynomials of the same degree
Recommended article: Q4892359
Recommended article: Maximal σ‐polynomials of connected 3‐chromatic graphs
Recommended article: On the roots of \(\sigma\)-polynomials
Recommended article: Q3565628
Recommended article: The search for chromatically unique graphs
description: scientific article; zbMATH DE number 205597