= Girth determines initial chromatic coefficients
For a finite <simple graph> on $n$ <vertices> with $m$ <edges> and no <graph cycle> shorter than $\ell$, the coefficient of $x^{n-i}$ in its <chromatic polynomial> is $(-1)^i\binom mi$ for $0\leq i\leq\min(n,\ell-2)$. In the <chromatic polynomial inclusion-exclusion formula>, an <edge> <subset> containing a <graph cycle> of length at least $\ell$ has $n-c(F)\geq\ell-1$. Thus every contribution to $x^{n-i}$ in this range is a <forest>, with exactly $i$ <edges>. Conversely, all $i$-<edge> <subsets> are <forests>, so precisely $\binom mi$ terms contribute, each with sign $(-1)^i$.
Back to article page
