Let $G$ be a connected graph with $n$ vertices and chromatic polynomial $p_G(x)$. Prove that:

a) $(-1)^{n-1}p_G(x) > 0$ for $0<x<1$.

b) $p_G(x)>0$ for $x>n-1$.

For a), the case of a tree is clear, having the explicit formula $p_G(x) = x(x-1)^{n-1}$. It might be possible to nicely use that any connected graph has a spanning tree, but unfortunately there is no nice inequality such as $p_H \leq p_G$ (or $\geq$) if $H$ is a subgraph of $G$. Similarly, for b) the complete graph case is nice and $G$ is necessarily a subgraph but this doesn't look enough.

Any help appreciated!

  • $\begingroup$ Actually, the first part can use the tree for an induction argument on the number of edges. Indeed, $p_G = p_{G-e} - p_{G/e}$ and $G-e$, $G/e$ satisfy the induction hypothesis and have $|G|$ and $|G|-1$ vertices. Then we are fine. The second part? $\endgroup$ – DesmondMiles Dec 25 '18 at 12:21

For the second part:

We can express the chromatic polynomial as a sum over partitions into independent sets. For every such partition $\{I_1, I_2, \dots, I_k\}$, there are $x^{|I_1|} (x-1)^{|I_2|} \dotsm (x-k+1)^{|I_k|}$ ways to color the graph by $x$ colors if we want to make $I_1, I_2, \dots, I_k$ be the color classes, divided by some constant term to account for symmetry. (Conversely, for every proper coloring of the graph by $x$ colors, the color classes form such a partition.)

For $x>n-1$, each factor in each $x^{|I_1|} (x-1)^{|I_2|} \dotsm (x-k+1)^{|I_k|}$ term is positive, and therefore the chromatic polynomial is positive.

  • $\begingroup$ Wow, amazing! Thanks a lot. $\endgroup$ – DesmondMiles Dec 25 '18 at 16:34

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.