Discrete CATS Seminar
U N I V E R S I T Y
K E N T U C K Y
WHERE CATS =
845 PATTERSON OFFICE TOWER
"Nowhere-harmonic colorings of graphs"
University of Kentucky
Monday, April 5, 2010
Proper vertex colorings of a graph are related to its
boundary map, also called its signed vertex-edge incidence matrix. The
vertex Laplacian of a graph, a natural extension of the boundary map,
leads us to introduce nowhere-harmonic colorings and analogues of the
chromatic polynomial and Stanley's theorem relating negative
evaluations of the chromatic polynomial to acyclic orientations.
Further, we discuss some examples demonstrating that nowhere-harmonic
colorings are more complicated from an enumerative perspective than
proper colorings. This is joint work with Matthias Beck.