Chromatic polynomials of partition systems Original Research Article

The theory of the umbral chromatic polynomial of a simplicial complex provides a combinatorial framework for the study of formal group laws over a commutative, torsion-free ring, and our aim in this work is to extend its definition to a class of set systems P, which we label partition systems. When suitably evaluated, our polynomial χψ(P; x) enumerates factorized colorings, as well as coloring forests of the partition system by type. These colorings are related to the Mullin-Rota concept of reluctant functions, and whenever P is a simplicial complex, they reduce to more familiar notions of coloring. Our three main results demonstrate how several properties of the classical chromatic polynomial χ(H;x), where H is a simple graph, may be generalized. Firstly, we prove that our polynomial χψ(P;x) retains the property of being expressible as the characteristic polynomial of an appropriate poset, which holds for χ(H; x) by virtue of Whitneyʹs original definition. Secondly, we provide two generalizations for the formula describing the chromatic polynomial of a disjoint union of graphs; one of these formulas depends explicitly on the context of partition systems and is not available when we restrict attention to graphs or simplicial complexes. Thirdly, we introduce partition systems with group action, thereby providing a combinatorial interpretation of normalized versions of our polynomials. In the case of the symmetric group acting on the trivial partition system, these are the normalized conjugate Bell polynomials, whose interpretation is a vital prerequisite for extending our framework to formal group laws over arbitrary rings of scalars; here, however, we concentrate solely on combinatorial aspects.