The protean chromatic polynomial

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.