Chromatic polynomial of non-tree graphs?

Question

If x ≥ 3 and G is not a tree, show that $χ(G, x) < x(x−1)^{n−1}$

I think if G is connected, the result is trivial.

How can I deal with the case that G is not connected?

Answer 1

In my answer to the Chromatic polynomial of connected graph $ \leq x(x-1)^{n-1}$, I explain how it's not true for the polynomials (giving a counterexample).

It's true if we restrict to non-negative integers, but this means we're counting $x$-colorings for $x \geq 0$ (and the polynomial is just a distraction).

In this question, $\chi(G, x) < x(x−1)^{n−1}$ is not true when $G$ is a tree. After changing $<$ to $\leq$ and restricting to non-negative integers, yes, it's not difficult (a $x$-coloring of $G$ gives an $x$-coloring of a spanning tree).

If we allow $G$ to be a disconnected graph, then it's not true even when $x$ is restricted to positive integers. An $n$-vertex graph with no edges has the chromatic polynomial $x^n$.