Ultimate chromatic polynomials
type: Item
instance of: scholarly article
title: Ultimate chromatic polynomials
zbMATH Open document ID: 0796.05035
DOI: 10.1016/0012-365X(94)90174-0
author: V. Pereyra
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 20K99
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 57T05
Mathematics Subject Classification ID: 05A40
zbMATH DE Number: 562677
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: free abelian group
zbMATH Keywords: poset
zbMATH Keywords: ultimate chromatic polynomial
zbMATH Keywords: colorings
zbMATH Keywords: Hopf algebras
zbMATH Keywords: umbral chromatic polynomial
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Q4770409
cites work: Two rings connected with the inclusion-exclusion principle
cites work: On the Möbius algebra of a partially ordered set
cites work: Coalgebras and Bialgebras in Combinatorics
cites work: Coclosure operators and chromatic polynomials.
cites work: Q3812261
cites work: Umbral interpolation and the addition/contraction tree for graphs
cites work: Bijective proofs of some classical partition identities
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Antipodes and incidence coalgebras
cites work: Q5590089
description: scientific article; zbMATH DE number 562677