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

117 Views Asked by At

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!

1

There are 1 best solutions below

1
On BEST ANSWER

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.