"Nowhere-harmonic colorings of graphs"

Ben Braun
University of Kentucky

Monday, April 5, 2010
4:00 pm
845 POT

Abstract:

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.