## Why is the chromatic polynomial a polynomial?

- Feb. 20, 2015
- 2:15 p.m.
- LeConte 312

## Abstract

More than 100 years ago G. Birkhoff found that counting the number of proper vertex k-colorings of a graph G, chi(G,k), is a polynomial in k. His proof relied on a recursion formula using deletion and contraction. We show that counting other graph colorings with k colors also gives rise to polynomials, although the proof is different. We then show that every graph polynomial is the counting function of some generalized coloring. (Joint work with T. Kotek and B. Zilber.)