Recursion Relations for Chromatic Coefficients for Graphs and Hypergraphs

Abstract

We establish a set of recursion relations for the coefficients in the chromatic polynomial of a graph or a hypergraph. As an application we provide a generalization of Whitney’s broken cycle theorem for hypergraphs, as well as deriving an explicit formula for the linear coefficient of the chromatic polynomial of the r-complete hypergraph in terms of roots of the Taylor polynomials for the exponential function.

Keywords

• chromatic polynomials
• hypergraphs
• broken cycles
• 05c15
• 05c65