Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations

Fengming Dong, Jun Ge, Helin Gong +3

The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum _{i=1}^n(-1{)}^{n-i}{a}_i{x}^i$, where $a_i$ is interpreted as the number of broken-cycle…