# Chromatic polynomial with constant sign on $x > n -1$ and $0<x<1$

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.

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!

• 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? – DesmondMiles Dec 25 '18 at 12:21

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.