6
$\begingroup$

I was talking to my brother today, and we came up with a little conjecture. Is it true that a graph $G$ of order $n$ is connected if and only if the coefficient of $x$ in the chromatic polynomial $P(G,x)$ is nonzero? This was inspired by results like the coefficient of $x^n$ is always $1$, the constant term is always $0$, the coefficient $x^{n-1}=-|E|$, etc.

We were able to prove one direction. Suppose $G$ is disconnected. Then $G$ is the union of disconnected components, say $H$ and $K$ for simplicity's sake, and so $P(G,x)=P(H,x)P(K,x)$. But since the constant term of a chromatic polynomial is always $0$, then the least term of $P(H,x)P(K,x)$ is at least $x^2$ since the least monomial term of each is $x$, and so the coefficient of $x$ is $0$.

However, we couldn't quite complete the other direction. Our idea was to take $G$ to be a connected graph. Then $G$ has a spanning tree, with chromatic polynomial $x(x-1)^{n-1}$, which has $(-1)^{n-1}$ as its coefficient for $x$. I figured you could then recover the original graph by adding edges back, and using the fact that $P(G,x)=P(G\setminus e,x)-P(G/e,x)$ to somehow induct, but we couldn't complete the argument. So is the reverse direction true? If so, how to prove it? And if not, is there a counterexample? Thank you.

  • 0
    sorry, not sure!2011-04-26

1 Answers 1

4

Wikipedia says your conjecture is correct. If $G$ has $k$ connected components, then the coefficient of $t^k$ in the chromatic polynomial is non-zero, and all the coefficient of $t^l$ for $l is zero. This pretty much sums up your result.

  • 1
    It's actually not really that much more general. Basically, the number of colorings of a disconnected graph with $k$ colors is triviallly the product of the number of colorings of each component, so this "general" rule actually follows from the specific rule for the connected graph (your conjecture.)2011-04-23