IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.)

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC