March 5, 2017

The protean chromatic polynomial

As part of the math department’s MAAD series, Bruce Sagan gave a fantastic talk titled: “The protean chromatic polynomial”.  His abstract follows:

Let t be a positive integer and let G be a combinatorial graph with vertices
V and edges E.  A proper coloring of G from a set with t colors is a function c :V →  {1, 2, …, t} such that if  uv ϵ E then c(u) ≠c(v), that is, the endpoints of an edge must be colored differently. These are the colorings considered in the famous Four Color Theorem. The chromatic polynomial of G, P(G; t), is the number of proper colorings of G from a set with t colors. It turns out that this is a polynomial in t with many amazing properties. One can characterize the degree and coefficients of P(G; t). There are also connections with acyclic orientations of G, hyperplane arrangements, symmetric functions, and Chern classes in algebraic geometry. This talk will survey some of these results.