zbMATH — the first resource for mathematics

On \(\sigma\)-polynomials and a class of chromatically unique graphs. (English) Zbl 0774.05039
The \(\sigma\)-polynomial of a graph was defined in \((*)\) 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 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.

05C15 Coloring of graphs and hypergraphs
05E05 Symmetric functions and generalizations
Full Text: DOI
[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Application (Elsevier. North-Holland, New York). · Zbl 1134.05001
[2] N. Biggs, Algebraic Graph Theory (Cambridge Univ. Press, Cambridge). · Zbl 0284.05101
[3] Korfhage, R.R., Σ-polynomials and graph colouring, J. combin. theory ser. B, 24, 137-153, (1978) · Zbl 0845.05043
[4] Frucht, R.W.; Giudici, R.E., Some chromatically unique graphs with seven points, Ars combin., 16A, 161-172, (1983) · Zbl 0536.05026
[5] Read, R.C., An introduction of chromatic polynomials, J. combin. theory, 4, 52-71, (1968) · Zbl 0173.26203
[6] Dhurandhar, M., Characterization of quadratic and cube σ-polynomials, J. combin. theory ser. B, 37, 210-220, (1984) · Zbl 0554.05030
[7] Xu, S.-J., On σ-polynomials, Discrete math., 69, 189-194, (1988) · Zbl 0658.05025
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.