# Sum of squares of chromatic roots of a bipartite graph

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!

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

• May I ask how one could get the $a_{2}$ equality in "It has been shown that ..."? Sep 22 at 13:17
• @1001 Thank you for the clarification, it's really helpful. Although given this equality, one could prove it by induction, but I was wondering that what if one doesn't have said equality, how could one obtain this? In other words, what are the intuitions behind $a_{2}$ and $k^{n - 2}$? Thank you. Sep 23 at 13:23