Graphs with linear coefficient of the chromatic polynomial is of modulus 1

75 Views Asked by At

Let $G$ be a graph with $n$ vertices and let $\chi_G$ be its chromatic polynomial.

Since $\chi_G(q) = q(q-1)^{n-1}$ for trees, we have that the linear coefficient is of unit modulus.

Is this condition also sufficient for a graph to be a tree? If so, how to prove this?

Thank you.

1

There are 1 best solutions below

1
On BEST ANSWER

It is sufficient. It is known that the absolute value of the linear coefficient of the chromatic polynomial counts the number of acyclic orientations of $G$ with some fixed $v \in V$ as their unique source, see the answer to this question.

Your statement easily follows from this: first, a non-connected graph has no such orientations, since each component must contain at least one source. Second, a connected graph that is not a tree has multiple such orientations: take a spanning tree of $G$ that contains every neighbour of $v$ and orient the edges of this tree away from $v$. Then we can orient the rest of the edges arbitrarily to get a suitable orientation, and since we can orient each extra edge in two ways, this method already gives us multiple orientations.