Richard Behr (Binghamton)

The Chromatic Polynomial

Abstract for the Combinatorics Seminar
2013 November 5

Introduced by George David Birkhoff in 1912, the Chromatic Polynomial is a graph invariant that counts the number of ways to properly color a graph as a function of the number of colors. The Chromatic Polynomial satisfies several important properties (Deletion-Contraction reducible, invariant under graph isomorphism, 0 on loops, and multiplicative over disjoint graphs), and it is universal for all graph invariants satisfying these properties, in the sense that every graph invariant satisfying these properties is an evaluation of the Chromatic Polynomial. I will prove this, as well as show some examples and other interesting properties.


To the Combinatorics Seminar Web page.