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 .
Articles by others on the same topic
There are currently no matching articles.