Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
I think 9.47 here gives you what you need –  Juan S Apr 23 '11 at 0:49
    
@Qwirk, thanks, I'll try to get a hold of that and take a deeper look. –  yunone Apr 23 '11 at 1:00
    
@Qwirk, I was looking around in that book, and in 9.39 they use the notation $f_{(n)}$, saying the coefficient of $x^{n-1}$ in $f_{(n)}$ is $-(1/2)(n)(n-1)$. Do you happen to know what this notation $f_{(n)}$ means? –  yunone Apr 23 '11 at 23:37
    
sorry, not sure! –  Juan S Apr 26 '11 at 23:44
add comment

1 Answer

up vote 4 down vote accepted

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<k$ is zero. This pretty much sums up your result.

share|improve this answer
    
Thanks Thomas, I guess this answers my question in more generality. –  yunone Apr 23 '11 at 18:18
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.) –  Thomas Andrews Apr 23 '11 at 18:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.