I'm studying chromatic numbers and chromatic polynomials of graphs at the moment and I know the subtle connection between the two:

Let $G$ be a graph, $\chi(G)$ be it's chromatic number and $p_G(x)$ be it's chromatic polynomial. Then $\chi(G)=\min\{k:p_G(k)>0\}$.

However, I'm wondering if we can say more than just that. I'm looking at whether there are any proofs or any counterexamples for my following claim:

Suppose $G$ and $H$ are graphs with $|G|=|H|$ and $e(G)=e(H)$. Then is the following true: $\chi(G)>\chi(H)\iff p_G(x)>p_H(x)$ for sufficiently large $x$.

I've managed to construct something which may be a counterexample but I don't quite seem to understand why (as in it doesn't intuitively seem to make sense).

My example: $G=C_3+e$ and $H=C_4$. Both have 4 edges and 4 vertices and $\chi(G)=3>2=\chi(H)$.

$p_G(x)=x^4-4x^3+6x^2-3x$ and $p_H(x)=x^4-4x^3+5x^2-2x-1$ which shows that $p_H(x)>p_G(x)$ for large $x$. I obtained $p_G(x)$ by using the formula known for cycles and obtained $p_H(x)$ by using the recurrence relation to reduce $H$ to $C_3$.

I may have made a careless mistake so I'd appreciate if somebody could check these for me.


This seems to be overlapping a lot with this question.

First of all, you have made some mistake in your computation (it is easy to spot that $p_H$ has a mistake: it cannot have a non-zero constant term). For the $G$ and $H$ you defined, the correct polynomials are $$ p_G(x) = x^4 - 4 x^3 + 5 x^2 - 2 x$$ $$ p_H(x) = x^4 - 4 x^3 + 6 x^2 - 3 x$$ So $p_G(x) < p_H(x)$ when $x$ is large.

Secondary, what you propose cannot work in either direction. See my answer to the question I have linked above. The large $x$ behavior of $p_G(x) - p_H(x)$ is not related to which one has the largest chromatic number, but to which one has the largest girth.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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