Applied Mathematics Colloquia by Bruce Sagan: The Protean Chromatic Polynomial
Speaker:
Bruce Sagan, professor of mathematics, Michigan State University
Title:
The Protean Chromatic Polynomial
Abstract:
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. For example, there are connections with acyclic orientations, hyperplane arrangements and symmetric functions. This talk will survey some of these results.
Applied Mathematics Colloquium