# On the degree-chromatic polynomial of a tree

Diego Cifuentes¹

¹Departamento de Matemáticas, Universidad de los Andes, Bogotá, Colombia

**Abstract.** The degree chromatic polynomial $P_m(G, k)$ of a graph $G$ counts the number of $k$-colorings in which no vertex has $m$ adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.

**Résumé.** Le polynôme degré chromatique $P_m(G, k)$ d'un graphe $G$ compte le nombre de $k$-colorations dans lesquelles aucun sommet n'a $m$ sommets adjacents de sa même couleur. On démontre la conjecture de Humpert et Martin sur les coefficients principaux du polynôme degré chromatique d'un arbre.

**Keywords:** chromatic polynomial, graph coloring, tree

George David Birkhoff defined the chromatic polynomial of a graph to attack the renowned four color problem. The chromatic polynomial $P(G, k)$ counts the $k$-colorings of a graph $G$ in which no two adjacent vertices have the same color [Read(1968)].

Given a graph $G$, Humpert and Martin defined its $m$-chromatic polynomial $P_m(G, k)$ to be the number of $k$-colorings of $G$ such that no vertex has $m$ adjacent vertices of its same color. They proved this is indeed a polynomial. When $m = 1$, we recover the usual chromatic polynomial of the graph.

The chromatic polynomial is of the form

$$P(G, k) = k^n - ek^{n-1} + o(k^{n-1}),$$

where $n$ is the number of vertices and $e$ the number of edges of $G$. For $m > 1$ the formula is no longer true, but Humpert and Martin conjectured the following formula which we now prove:

**Theorem 1 ([Humpert and Martin(2010), Humpert and Martin(2011)], Conjecture)** Let $T$ be a tree with $n$ vertices and let $m$ be an integer with $1 < m < n$, then the following equation holds.

$$P_m(T, k) = k^n - \sum_{v \in V(T)} \binom{d(v)}{m} k^{n-m} + o(k^{n-m})$$

**Proof:** For a given coloring of $T$, say vertices $v_1$ and $v_2$ are “friends” if they are adjacent and have the same color. For each $v$, let $A_v$ be the set of colorings such that $v$ has at least $m$ friends. We want to find the number of colorings which are not in any $A_v$, and we will use the inclusion-exclusion principle. As the total number of $k$-colorings is $k^n$, we have

$$P_m(T, k) = k^n - \sum_{v \in V} |A_v| + \sum_{v_1, v_2 \in V} |A_{v_1} \cap A_{v_2}| - \dots$$
We first show that $|A_v| = \binom{d(v)}{m}k^{n-m} + o(k^{n-m})$. Let $A_v^{(l)}$ be the set of $k$-colorings such that $v$ has exactly $l$ friends. In order to obtain a coloring in $A_v^{(l)}$, we may choose the $l$ friends in $\binom{d(v)}{l}$ ways, the color of $v$ and its friends in $k$ ways, the color of the remaining adjacent vertices to $v$ in $(k-1)^{d(v)-l}$ ways, and the color of the rest of the vertices in $k^{n-1-d(v)}$ ways. Then

$$|A_v| = \sum_{l=m}^{n-1} |A_v^{(l)}| = \sum_{l=m}^{n-1} \binom{d(v)}{l} k^{n-d(v)} (k-1)^{d(v)-l} \\ = \binom{d(v)}{m} k^{n-m} + o(k^{n-m}).$$

To complete the proof, it is sufficient to see that for any set $S$ of at least 2 vertices $|\bigcap_{v \in S} A_v| = o(k^{n-m})$; clearly we may assume $S = \{v_1, v_2\}$. Consider the following cases:

**Case 1** $v_1$ and $v_2$ are not adjacent.

Split $A_{v_1}$ into equivalence classes with the equivalence relation

$$\sigma_1 \sim \sigma_2 \Leftrightarrow \sigma_1(w) = \sigma_2(w) \text{ for all } w \neq v_2.$$

Note that each equivalence class $C$ consists of $k$ colorings, which only differ in the color of $v_2$. In addition, for each $C$ at most $\frac{d(v_2)}{m}$ of its colorings are in $A_{v_2}$, as if $\sigma \in A_{v_2}$ there must be $m$ vertices adjacent to $v_2$ with the color $\sigma(v_2)$. Therefore

$$|A_{v_1} \cap A_{v_2}| = \sum_C |C \cap A_{v_2}| \le \sum_C \frac{d(v_2)}{m} = \frac{|A_{v_1}|}{k} \cdot \frac{d(v_2)}{m}.$$

It follows that $\frac{|A_{v_1} \cap A_{v_2}|}{|A_{v_1}|}$ goes to 0 as $k$ goes to infinity, so $|A_{v_1} \cap A_{v_2}| = o(k^{n-m})$.

**Case 2** $v_1$ and $v_2$ are adjacent.

Let $W$ be the set of adjacent vertices to $v_2$ other than $v_1$. They are not adjacent to $v_1$ as $T$ has no cycles. Split $A_{v_1}$ into equivalence classes with the equivalence relation

$$\sigma_1 \sim \sigma_2 \Leftrightarrow \sigma_1(w) = \sigma_2(w) \text{ for all } w \notin W.$$

Each equivalence class $C$ consists of $k^{|W|}$ colorings, which may only differ in the colors of the vertices in $W$. If $v_1$ and $v_2$ are friends in the colorings of $C$, then a coloring in $|C \cap A_{v_2}|$ must contain at least $m-1$ vertices in $W$ of the same color as $v_2$. Therefore

$$|C \cap A_{v_2}| = \sum_{l=m-1}^{|W|} \binom{|W|}{l} (k-1)^{|W|-l} < \sum_{l=0}^{|W|} \binom{|W|}{l} k^{|W|-1} = 2^{|W|} k^{|W|-1}.$$

Notice that here we are using $m \ge 2$ so that $l \ge 1$. Otherwise, if $v_1$ and $v_2$ are not friends in the colorings of $C$, then
$$|C \cap A_{v_2}| = \sum_{l=m}^{|W|} \binom{|W|}{l} (k-1)^{|W|-l} < \sum_{l=0}^{|W|} \binom{|W|}{l} k^{|W|-1} = 2^{|W|} k^{|W|-1}.$$

Therefore

$$|A_{v_1} \cap A_{v_2}| = \sum_C |C \cap A_{v_2}| < \sum_C 2^{|W|} k^{|W|-1} \\ = \frac{|A_{v_1}|}{k^{|W|}} \cdot 2^{|W|} k^{|W|-1} = \frac{|A_{v_1}| \cdot 2^{|W|}}{k}$$

and $|A_{v_1} \cap A_{v_2}| = o(k^{n-m})$ follows as in the first case.

This completes the proof of the theorem. □

## Acknowledgements

I would like to thank Federico Ardila for bringing this problem to my attention, and for helping me improve the presentation of this note. I would also like to acknowledge the support of the SFSU-Colombia Combinatorics Initiative and the Universidad de los Andes.

## References

[Humpert and Martin(2010)] B. Humpert and J. L. Martin. The incidence Hopf algebra of graphs. Preprint arXiv:1012.4786, 2010.

[Humpert and Martin(2011)] B. Humpert and J. L. Martin. The incidence Hopf algebra of graphs. *DMTCS Proceedings*, 0(01), 2011. ISSN 1365-8050. URL http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmA00146.

[Read(1968)] R. C. Read. An introduction to chromatic polynomials. *Journal of Combinatorial Theory*, 4(1):52–71, 1968.