Kaitlin Reissig (Binghamton)

Stanley's Theorem on Acyclic Orientations and Colorings of Graphs

Abstract for the Combinatorics Seminar
2012 November 20

The chromatic polynomial of a graph, evaluated at positive integers, counts proper colorings of the graph. Richard Stanley proved that the evaluation at negative integers also counts something, specifically, compatible pairs of colorings and acyclic orientations. In particular, the evaluation at −1 counts acyclic orientations. I will present this influential theorem and its proof, as well as some consequences.


To the Combinatorics Seminar Web page.