On \(\sigma\)-polynomials and a class of chromatically unique graphs (Q1801695)

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.