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 - https://www.scopus.com/pages/publications/82055194140
UR - https://www.scopus.com/pages/publications/82055194140#tab=citedBy
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 -