On graphs having \(\sigma\)-polynomials of the same degree (Q1208359): Difference between revisions

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)].