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

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. Integer-point enumeration in polyhedra. MR**2271992****2.**Matthias Beck and Thomas Zaslavsky,*Inside-out polytopes*, Adv. Math.**205**(2006), no. 1, 134–162. MR**2254310**, 10.1016/j.aim.2005.07.006**3.**Matthias Beck and Thomas Zaslavsky,*The number of nowhere-zero flows on graphs and signed graphs*, J. Combin. Theory Ser. B**96**(2006), no. 6, 901–918. MR**2274083**, 10.1016/j.jctb.2006.02.011**4.**Norman Biggs,*Algebraic graph theory*, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR**1271140****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**, 10.2307/1967597**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**, 10.1016/j.ejc.2008.01.022**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**, 10.1006/jctb.2001.2081**10.**Martin Kochol,*Tension polynomials of graphs*, J. Graph Theory**40**(2002), no. 3, 137–146. MR**1905130**, 10.1002/jgt.10038**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**, 10.4310/SDG.2004.v9.n1.a7**13.**Paolo M. Soardi,*Potential theory on infinite networks*, Lecture Notes in Mathematics, vol. 1590, Springer-Verlag, Berlin, 1994. MR**1324344****14.**Richard P. Stanley,*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171–178. MR**0317988****15.**Richard P. Stanley,*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****16.**Hassler Whitney,*A logical expansion in mathematics*, Bull. Amer. Math. Soc.**38**(1932), no. 8, 572–579. MR**1562461**, 10.1090/S0002-9904-1932-05460-X

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:
http://dx.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.