The chromatic polynomial $P(G,k)$ counts all vertex colorings with $k$ or fewer colors.
But is there a polynomial that can count vertex colorings with exactly $k$ colors?
If you simply take the difference $P(G,k) – P(G,k-1)$, the degeneracy of color-set choices is not taken into account. For example, with $k$=4 colors, the many ways of selecting a set of 3 colors (from 4 possible) each constitute a distinct color palette, but are only deducted once using the above technique.
Perhaps you just take this into account in a straightforward way?
Best Answer
If we name the hypothetical function $f_G(k)$ then we see that $$\chi_G(k) = \sum_{i=0}^{k} \binom{k}{i} f_G(i)$$
If $f_G$ is a polynomial, $f_G(x) = \Theta(x^a)$ for some $a$, then $\chi_G(2x)$ has a term $\binom{2x}{x} f_G(x)$, and in particular is not bounded by any polynomial. In fact, we can conclude that $f_G(x)$ must be asymptotically bounded by $a^{-x}$ for some $a > 1$.
An alternative perspective is to note that if $k > V$ then $f_G(k) = 0$. The only polynomial which has infinitely many roots is $P(x) = 0$.
Either way, we see that $f_G(k)$ is not a polynomial.