zbMATH — the first resource for mathematics

On graphs having \(\sigma\)-polynomials of the same degree. (English) Zbl 0771.05038
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 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 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 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 R. W. Frucht and R. E. Giudici [Ars. Comb. 16-A, 161-172 (1983; Zbl 0536.05026)].

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Dhurandhar, M., Characterization of quadratic and cubic σ-polynomials, J. combin. theory ser. B, 37, 210-220, (1984) · Zbl 0554.05030
[2] Frucht, R.W.; Giudici, R.E., Some chromatically unique graphs with seven points, Ars combin., 16-A, 161-172, (1983) · Zbl 0536.05026
[3] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[4] Korfhage, R.R., σ-polynomials and graph coloring, J. combin. theory ser. B, 24, 137-153, (1978) · Zbl 0845.05043
[5] Li, N.-Z.; Whitehead, E.G., Graph theory and its applications: east and west, Ann. N.Y. acad. sci., 576, 328-335, (1989), Classification of graphs having cubic σ-polynomials
[6] Read, R.C., An introduction to chromatic polynomials, J. combin. theory, 4, 52-71, (1968) · Zbl 0173.26203
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.