Ultimate chromatic polynomials (Q1322289)

An approach to enumeration problems relying on the algebra of free abelian groups is outlined. The main application is a generalization of the chromatic polynomial of a simple graph \(G\) to the ``ultimate chromatic polynomial'', which lies in the free abelian group generated by the poset \(K(G)\) of contractions of \(G\), and which reduces to the usual chromatic polynomial by a simple substitution. The main properties of the ultimate chromatic polynomial are given in terms of an evaluation homomorphism for each positive integer \(t\), which when applied to the polynomial gives an explicit list of the colorings of \(G\) with \(t\) colors. By considering posets larger than \(K(G)\) and enriching the algebra accordingly, the authors extend their construction to incorporate the corresponding incidence Hopf algebras. The enriched polynomial reduces, by a similar substitution, to the umbral chromatic polynomial of \(G\), see \textit{N. Ray} and \textit{C. Wright} [Ars. Comb. 25B, 277-286 (1988; Zbl 0662.05023)].