Discrete Math Seminar Spring 2009
The chromatic polynomial via homology
Justin DeVries, UNL;
Apr 7
The chromatic polynomial of a graph is the function counting the number of
vertex k-colorings, originally invented to attack the Four Color Problem.
Partially motivated by ideas from combinatorial commutative algebra,
Steingrimsson defined the coloring ideal and coloring complex of a graph,
relating the chromatic polynomial to other well-studied functions in
commutative algebra. Recent work has shown that the homology of the
coloring complex is sufficient to determine the chromatic polynomial, in
fact one can literally read off the polynomial from a Hodge decomposition.
We'll discuss these results and all necessary background; no knowledge of
commutative algebra will be assumed (and truthfully, we won't need much).