# Chromatic Number and Chromatic Polynomial of a Graph

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.

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.