On graphs having \(\sigma\)-polynomials of the same degree
type: Item
instance of: scholarly article
title: On graphs having \(\sigma\)-polynomials of the same degree
zbMATH Open document ID: 0771.05038
DOI: 10.1016/0012-365X(92)90707-M
author: Nian Zu Li
published in: Discrete Mathematics
publication date: 1993-05-16T00:00:00Z
review text: The graphs considered in this paper are finite and undirected, with no loops or parallel edges. The \(\sigma\)-polynomial \(\sigma(G,t)\) of a graph \(G\) with \(p\) vertices is defined in \textit{R. R. Korfhage} [\(\sigma\)- polynomials and graph coloring, J. Comb. Theory, Ser. B 24, No. 2, 137- 153 (1978)] as follows: if the chromatic polynomial \(p(G,\lambda)\) of \(G\) is \(\sum^{p-\chi(G)}_{i=0}a_ i\lambda(\lambda-1)\cdots(\lambda-(p- i)+1)\), where \(\chi(G)\) is the chromatic number of \(G\), then \(\sigma(G,t)=\sum^{p-\chi(G)}_{i=0}a_ it^{p-\chi(G)-i}\). A theorem in \textit{R. C. Read} [An introduction to chromatic polynomials, J. Comb. Theory 4, 52-71 (1967; Zbl 0173.262)] which identifies \(a_ i\) as the number of subgraphs of the complement of \(G\) which are isomorphic to the union of complete graphs with a total of \(i\) vertices, is used to obtain a necessary and sufficient condition for the degree \(p-\chi(G)\) of \(\sigma(G,t)\) to be \(k\) for any positive integer \(k\). This generalizes the condition found in the above-mentioned paper of R. R. Korfhage for \(k=0\) and 1 and in \textit{M. Dhurandhar} [J. Comb. Theory, Ser. B 37, 210- 220 (1984; Zbl 0554.05030)]. This condition is then used to construct all the graphs whose \(\sigma\)-polynomials are of degree 2, 3 and 4; the results for degree 2 agree with those in \textit{R. W. Frucht} and \textit{R. E. Giudici} [Ars. Comb. 16-A, 161-172 (1983; Zbl 0536.05026)].
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 166360
zbMATH Keywords: \(\sigma\)-polynomial
zbMATH Keywords: chromatic number
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Characterization of quadratic and cubic \(\sigma\)-polynomials
cites work: Q3320409
cites work: Parallel concepts in graph theory
cites work: \(\sigma\)-polynomials and graph coloring
cites work: Q4294609
cites work: An introduction to chromatic polynomials
description: scientific article; zbMATH DE number 166360