TY - JOUR

T1 - Nowhere-harmonic colorings of graphs

AU - Beck, Matthias

AU - Braun, Benjamin

PY - 2012

Y1 - 2012

N2 - Proper vertex colorings of a graph are related to its boundary map ∂1, also called its signed vertex-edge incidence matrix. The vertex Laplacian of a graph, L = ∂1∂t1, 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 several examples demonstrating that nowhere-harmonic colorings are more complicated from an enumerative perspective than proper colorings.

AB - Proper vertex colorings of a graph are related to its boundary map ∂1, also called its signed vertex-edge incidence matrix. The vertex Laplacian of a graph, L = ∂1∂t1, 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 several examples demonstrating that nowhere-harmonic colorings are more complicated from an enumerative perspective than proper colorings.

KW - Boundary map

KW - Chromatic polynomial

KW - Graph laplacian

KW - Hyperplane arrangement

KW - Inside-out polytope

KW - Nowhere-harmonic coloring

UR - http://www.scopus.com/inward/record.url?scp=82055194140&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=82055194140&partnerID=8YFLogxK

U2 - 10.1090/S0002-9939-2011-10879-7

DO - 10.1090/S0002-9939-2011-10879-7

M3 - Article

AN - SCOPUS:82055194140

SN - 0002-9939

VL - 140

SP - 47

EP - 63

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

IS - 1

ER -