Let $P\_{H}(G, t)$ be the number of vertex colorings of a graph $G$ in $t$ colors that avoid having a monochromatic subgraph $H$. In particular, for $H$ given by a single edge we recover the usual chromatic polynomial $P\_{H}(G, t) = P(G, t)$.


Question: Are there easy proofs that $P\_{H}(G, t)$ is a polynomial for $t \geq 0$ ?



Subgraph avoiding colorings
Fix a partition onto non-empty color classes (there are finitely many ways to do so, denote by $k$ the number of distinct color classes) without monochromatic $H$. After that, there is $t(t-1)\ldots(t-k+1)$ ways to assign colors. Sum up, you still get a polynomial.


