Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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 $ \partial_1$, also called its signed vertex-edge incidence matrix. The vertex Laplacian of a graph, $ L=\partial_1 \partial_1^t$, 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.

References [Enhancements On Off] (What's this?)

  • 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,, 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 Software package IOP available at
  • 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 $ n$-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

Similar Articles

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

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

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.

American Mathematical Society