Sum of squares of chromatic roots of a bipartite graph

Question

Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots of the graph $G$ is equal to the number of edges $e(G)$.

I am working on a problem and it somehow is related to the following pattern, which I also experiment with SageMath:

Want to prove: Given a bipartite graph $G$ of minimum degree $2$ and $G$ is not a forest, with its chromatic polynomial $P(G, k)$ and chromatic roots $r_{1}, r_{2}, \ldots, r_{n}$, then we have

$$\sum_{i = 1}^{n} r_{i}^{2} = e(G)$$

However, I could not seem to prove it. I tried some Cauchy-Schwarz inequality calculations. I also couldn't find relevant literatures containing this result, or relevant research on (complex) chromatic roots of bipartite graphs.

Thank you!

Answer 1

Consider the chromatic polynomial as a sum of monomials: $$P(G, k) = (k - r_1)(k - r_2)\cdots(k - r_n) = k^n + a_1k^{n-1} + \cdots + a_{n-1}k + a_n$$ It has been shown that $a_2 = \binom{e(G)}{2} - c_3(G)$, where $c_3(G)$ is the number of triangles in $G$.

For bipartite (and triangle-free graphs in general), we have $a_2 = \binom{e(G)}{2}$. It follows that \begin{align}\sum_{i=1}^n r_i^2 &= (-r_1-r_2-\cdots -r_n)^2 - 2(r_1r_2 + r_1r_3 + \cdots +r_{n-1}r_n)\\ &= a_1^2 - 2a_2\\ &= e(G)^2 - 2 \binom{e(G)}{2}\\ &= e(G)\end{align}

---

To prove that $a_2 = \binom{e(G)}{2} - c_3(G)$, you could use induction. As a base case, observe that the identity holds for empty graphs. For the induction step, recall that $$P(G, k) = P(G - uv, k) - P(G / uv, k)$$ and express the relevant coefficients of the two smaller graphs assuming the induction hypothesis:

• The third coefficient of $P(G - uv, k)$ is $$\binom{e(G - uv)}{2} - c_3(G - uv) = \binom{e(G) - 1}{2} - (c_3(G) - |N(u) \cap N(v)|).$$

• The second coefficient of $P(G / uv, k)$ (note that this polynomial has degree one smaller) is $$-e(G / uv) = - e(G) + |N(u) \cap N(v)|.$$ (Here you need $a_2 = - e(G)$, but that can again be proven by induction.)