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.
Best Answer
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.