4
$\begingroup$

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

$\endgroup$

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.