On the real roots of the chromatic polynomial

618 Views Asked by At

If $\chi_G(k)$ is the chromatic polynomial of graph $G$ on $n$ vertices, we want to prove the following statements:

  1. The only real root $x<1$ for $\chi_G(k)$ except for $x=0$.
  2. There is no real root $x>n$ for $\chi_G(k)$.

Things that I have tried:

  1. I can show that the terms of the chromatic polynomial alternate in sign. This means that there is no negative root. But still cannot handle the interval $(0,1)$.
  2. By definition of the chromatic polynomial, it is obvious that there is no integer root. But hard to say something about the real roots.

Any help is appreciated.

1

There are 1 best solutions below

4
On

For the first question: if for some $y$ in (0, 1), we have $P(G, y)=0$, then we know $P(G\setminus e, y)= P(G/e, y)$. Since all the efficients of chromatic polynomial are integers and $\deg P(G\setminus e, x)=n$, $\deg P(G/e, x)=n-1$, we can compare the number of digits after demical and conclude that it is impossible.