Graph coloring with exactly k-colors 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?
 A: 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.
A: Let $S \subseteq \{1,2,3,4\}=S_0$, and let $P_S$ be the number of proper colorings of $G$ that use either $S$ or a subset of $S$. Let $P'_S$ be the number of proper colorings of $S$ that use all of $S$ ie., every color of $S$ is used in the coloring.
Then by Inclusion-Exclusion:
$$P'_{S_0} = P_{S_0} -\sum_{S: |S|=3} P_S + \sum_{S: |S|=2} P_S - \sum_{S: |S|=1} P_S$$
or to use the notation in the statement of the problem, where $P'(G,k)$ is the number of colourings of $G$ that use all $k$ colors:
$$P'(G,4) = P(G,4)-4P(G,3)+6P(G,2)-4P(G,1)$$
