3
$\begingroup$

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!

$\endgroup$

1 Answer 1

6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ May I ask how one could get the $a_{2}$ equality in "It has been shown that ..."? $\endgroup$
    – hedgehog0
    Sep 22, 2023 at 13:17
  • 1
    $\begingroup$ I added a proof $\endgroup$
    – 1001
    Sep 23, 2023 at 1:15
  • 1
    $\begingroup$ @hedgehog0: If you know how to compute the chromatic polynomial in terms of the bond lattice of the graph (and its Möbius function), you can also see it from that. $\endgroup$ Sep 23, 2023 at 1:29
  • $\begingroup$ @SamHopkins Thank you for the clarification, unfortunately I don't know, but I will check it out... $\endgroup$
    – hedgehog0
    Sep 23, 2023 at 12:03
  • $\begingroup$ @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. $\endgroup$
    – hedgehog0
    Sep 23, 2023 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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