Necessary condition for a chromatic polynomial (Q1968570): Difference between revisions

The author proves that if \(P(t)=\sum _{k=0}^{n}a_{k}t^{k}\) is the chromatic polynomial of some graph \(G\) of order \(n\), then the numbers \(\sigma _{j}=\sum _{k=j}^{n}S(k,j)a_{k}\) have the following properties: there exists an index with \(0\leq k_{0}\leq n-1\) such that \(\sigma _{n},\sigma _{n-1},\ldots ,\sigma _{k_{0}+1}>0\) but \(\sigma _{k_{0}}=\sigma _{k_{0}-1}=\ldots =\sigma _{0}=0\). This provides a necessary condition for a polynomial to be the chromatic polynomial of some graph. Reviewer's remark: The property is obvious since \(\sigma _{j}=\text{Col}_{k}(G)\), the number of chromatic partitions with \(j\) classes of \(V(G)\), and \(k_{0}= \chi (G)-1\).