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$ ?
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.
Let the vertices be $x_1, ..., x_n$. Let $X$ be the set $\{a:\text{the subgraph of } G \text{ induced by the vertex set }a \cong H \}$
Consider the number of assignments of $1 ... t$ to $x_1, ..., x_n$ such that the constraints "Not all of $x_k$ $(k\in a)$ have the same value" are satisfied for all $a\in X$. These assignments correspond to the colorings that avoid having a monochromatic $H$.
Now I will prove the number is polynomial in $t$ for any family of sets $X$ on $1 ... n$. The proof is based on induction on the number of vertices and then the size of $X$.
The statement is of course true for an empty set of vertices. Say the statement is true for all numbers of vertices less than $n$.
$X= \emptyset$. Trivial.
Suppose the number is polynomial for $|X|=m-1$. Then, for $X'=X \cup \{x\}$, (the number of solutions violating at least one constraint in $X'$)=(the number of solutions violating at least one constraint in $X$)+(the number of solutions violating the constraint on $x$)-(the number of solutions violating at least one constraint in $X$ and the constraint on $x$) by the inclusion-exclusion principle.
If $x$ is empty or having only one element, all solutions would violate the constraint on $x$ so the statement is true. So we will assume $x$ has at least $2$ elements.
The first term on the RHS is polynomial in $k$ by induction on size of $X$.
The second term is polynomial by simple counting.
The third term is polynomial by replacing all the $x_a$ $(a \in x)$ by a single variable (because all the $x_a$ are equal) in order to reduce the number of varibles, and it's polynomial by induction on $n$.
So the number of solutions violating at least one constraint in $X'$ is polynomial in $k$, and thus, the number of solutions satisfying all constraints in $X'$ is polynomial in $k$.
By the use of mathematical induction on the size of $X$, we can prove the statement for every $n$ assuming its truth for every smaller $n$.
By the use of mathematical induction on $n$, the statement is true for any $n$.
Yes, $P_H(G,t)$ is just the chromatic polynomial of the hypergraph whose vertices are the vertices of $G$ and whose edges are the vertex sets of subgraphs of $G$ that are isomorphic to $H$.
The fact that the so-called chromatic polynomial is actually a polynomial is proved for hypergraphs in the same way as for graphs.
Suppose $G$ has order [number of vertices] $n$, and contains $m$ copies of $H$ as subgraphs (in the special case $H = K_2$, $m$ will be the size of $G$), and label them $H_1, H_2, \ldots, H_m$. (Some of them may share common vertices, which is not an issue). Let $r$ be the order of $H$.
Fix $t$, the number of colours available.
Let $N(H_i)$ be the number of colourings of $G$ in which $H_i$ is monochromatic. More generally, let $N(H_{i_1}, \ldots, H_{i_k})$ be the number of colourings in which each of $H_{i_1}, \ldots, H_{i_k}$ is monochromatic (not necessarily of the same colour). This will always be a power of $t$, and the power depends only on the structure of $G$ and $H$ (not on the value of $t$ itself), as shown below.
By the Inclusion-Exclusion Principle, the number of ways of colouring $G$ with $t$ colours such that none of the $H_i$s is monochromatic is \begin{equation*} P_H(G, t) = t^n - \sum_{i} N(H_i) + \sum_{i < j} N(H_i, H_j) - \cdots + (-1)^k \sum_{i_1 < \cdots < i_k} N(H_{i_1}, \ldots, H_{i_k}) + \cdots + (-1)^m N(H_1, \ldots, H_m) \end{equation*}
which is a polynomial in $t$ since each term is a power of $t$ (in terms of $n$ and $r$).
First, observe that $N(H_i) = t^{n - r + 1}$. That is, as $H_i$ is monochromatic, all its vertices must be assigned any one of the $t$ colours, which can be done in $t$ ways. The remaining $n - r$ vertices of $G$ must each be assigned a colour as well, which can be done in a total of $t^{n - r}$ ways. Thus, there are $t^{n - r + 1}$ colours in total, with $H_i$ monochromatic.
Now, consider $N(H_i, H_j)$. If $H_i$ and $H_j$ have no common vertices, then whatever be the value of $t$, $N(H_i, H_j) = t^{n - 2r + 2}$. If $H_i$ and $H_j$ have at least one common vertex, then both of them must be assigned the same colour, and hence $N(H_i, H_j) = t^{n - 2r + 1}$. Note that the power is independent of $t$ and is determined solely by the graph structure.
Generalising, consider $N(H_{i_1}, \ldots, H_{i_k})$. Again, depending (only) on the distribution of shared vertices among these subgraphs, the set $\{H_{i_1}, \ldots, H_{i_k}\}$ can be partitioned into some $p$ number of parts, and then $N(H_{i_1}, \ldots, H_{i_k}) = t^{n - kr + p}$ (all the subgraphs in each of the $p$ parts receive the same colour, so there $t^p$ independent ways of colouring these $H_i$s monochromatically; then the remaining $n - kr$ vertices can be coloured in $t^{n - kr}$ ways).
Note: I think Fedor Petrov's answer is the simplest one so far, but to my mind, my answer is also intuitively quite simple and occurred to me immediately because I have thought about the usual graph colouring problem along the same lines before. But writing down the formal argument does take time.
