# Subgraph avoiding colorings

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

#### Proof that the powers depend only the graph structure

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.