Graph coloring with exactly k-colors

Question

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?

Answer 1

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.

Answer 2

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)$$