Ultimate chromatic polynomials

✍ Scribed by Nigel Ray; William Schmitt

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 844 KB
• Volume: 125
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)90174-0

✦ Synopsis

We outline an approach to enumeration problems which relies on the algebra of free abelian groups, giving as our main application a generalisation of the chromatic polynomial of a simple graph G. Our polynomial lies in the free abelian group generated by the poset K(G) of contractions of G, and reduces to the classical case after a simple substitution. Its main properties may be stated in terms of an evaluation homomorphism, one for each positive integer t, which when applied to the polynomial yields an explicit list of the colourings of G with t colours. Considering posets larger than K(G), and enriching the algebra accordingly, we extend the whole construction to incorporate the corresponding incidence Hopf algebras. The enriched polynomial reduces by a similar substitution to the umbra1 chromatic polynomial of G.