Nowhere-harmonic colorings of graphs

Authors:
Matthias Beck and Benjamin Braun

Journal:
Proc. Amer. Math. Soc. **140** (2012), 47-63

MSC (2010):
Primary 05C78; Secondary 05A15, 52B20, 52C35

DOI:
https://doi.org/10.1090/S0002-9939-2011-10879-7

Published electronically:
May 9, 2011

MathSciNet review:
2833516

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 several examples demonstrating that nowhere-harmonic colorings are more complicated from an enumerative perspective than proper colorings.

**1.**Matthias Beck and Sinai Robins,*Computing the continuous discretely*, Undergraduate Texts in Mathematics, Springer, New York, 2007. MR**2271992 (2007h:11119)****2.**Matthias Beck and Thomas Zaslavsky,*Inside-out polytopes*, Adv. Math.**205**(2006), no. 1, 134-162. MR**2254310 (2007e:52017)****3.**-,*The number of nowhere-zero flows on graphs and signed graphs*, J. Combin. Theory Ser. B**96**(2006), no. 6, 901-918. MR**2274083 (2007k:05084)****4.**Norman Biggs,*Algebraic graph theory*, second ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR**1271140 (95h:05105)****5.**George D. Birkhoff,*A determinant formula for the number of ways of coloring a map*, Ann. of Math. (2)**14**(1912/13), no. 1-4, 42-46. MR**1502436****6.**Felix Breuer and Raman Sanyal,*Ehrhart theory, modular flow reciprocity, and the Tutte polynomial*, http://arxiv.org/abs/0907.0845, to appear in Math. Z. DOI: 10.1007/s00209-010-0782-6**7.**Beifang Chen and Jue Wang,*The flow and tension spaces and lattices of signed graphs*, European J. Combin.**30**(2009), no. 1, 263-279. MR**2460231****8.**Andrew Van Herick,*Theoretical and computational methods for lattice point enumeration in inside-out polytopes*, MA thesis, San Francisco State University, 2007. Available at`http://math.sfsu.edu/beck/teach/masters/andrewv.pdf`. Software package`IOP`available at`http://iop.sourceforge.net/`.**9.**Martin Kochol,*Polynomials associated with nowhere-zero flows*, J. Combin. Theory Ser. B**84**(2002), no. 2, 260-269. MR**1889258 (2002k:05193)****10.**-,*Tension polynomials of graphs*, J. Graph Theory**40**(2002), no. 3, 137-146. MR**1905130 (2003f:05048)****11.**Ross La Haye,*Binary relations on the power set of an -element set*, J. Integer Seq.**12**(2009), no. 2, Article 09.2.6, 15. MR**2486261****12.**László Lovász,*Discrete analytic functions: An exposition*, Surveys in Differential Geometry. Vol. IX, Surv. Differ. Geom., IX, Int. Press, Somerville, MA, 2004, pp. 241-273. MR**2195410 (2007g:30067)****13.**Paolo M. Soardi,*Potential theory on infinite networks*, Lecture Notes in Mathematics, vol. 1590, Springer-Verlag, Berlin, 1994. MR**1324344 (96i:31005)****14.**Richard P. Stanley,*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171-178. MR**0317988 (47:6537)****15.**-,*Enumerative combinatorics. Vol. 1*, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997, with a foreword by Gian-Carlo Rota. Corrected reprint of the 1986 original. MR**1442260 (98a:05001)****16.**Hassler Whitney,*A logical expansion in mathematics*, Bull. Amer. Math. Soc.**38**(1932), no. 8, 572-579. MR**1562461**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2010):
05C78,
05A15,
52B20,
52C35

Retrieve articles in all journals with MSC (2010): 05C78, 05A15, 52B20, 52C35

Additional Information

**Matthias Beck**

Affiliation:
Department of Mathematics, San Francisco State University, San Francisco, California 94132

Email:
beck@math.sfsu.edu

**Benjamin Braun**

Affiliation:
Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506-0027

Email:
benjamin.braun@uky.edu

DOI:
https://doi.org/10.1090/S0002-9939-2011-10879-7

Keywords:
Nowhere-harmonic coloring,
chromatic polynomial,
boundary map,
graph Laplacian,
inside-out polytope,
hyperplane arrangement.

Received by editor(s):
July 13, 2010

Received by editor(s) in revised form:
November 2, 2010

Published electronically:
May 9, 2011

Additional Notes:
This research was partially supported by the NSF through grants DMS-0810105 (first author) and DMS-0758321 (second author). The authors would like to thank Tom Zaslavsky and the anonymous referees for their comments and suggestions.

Communicated by:
Jim Haglund

Article copyright:
© Copyright 2011
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.