Girth determines initial chromatic coefficients

ID: girth-determines-initial-chromatic-coefficients

For a finite simple graph on vertices with edges and no graph cycle shorter than , the coefficient of in its chromatic polynomial is for . In the chromatic polynomial inclusion-exclusion formula, an edge subset containing a graph cycle of length at least has . Thus every contribution to in this range is a forest, with exactly edges. Conversely, all -edge subsets are forests, so precisely terms contribute, each with sign .

New to topics? Read the docs here!