Nowhere-harmonic colorings of graphs

Beck, Matthias; Braun, Benjamin

doi:10.1090/S0002-9939-2011-10879-7

Nowhere-harmonic colorings of graphs
HTML articles powered by AMS MathViewer

by Matthias Beck and Benjamin Braun

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

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

Published electronically: May 9, 2011

PDF | Request permission

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

Matthias Beck and Sinai Robins, Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2007. Integer-point enumeration in polyhedra. MR 2271992
Matthias Beck and Thomas Zaslavsky, Inside-out polytopes, Adv. Math. 205 (2006), no. 1, 134–162. MR 2254310, DOI 10.1016/j.aim.2005.07.006
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, DOI 10.1016/j.jctb.2006.02.011
Norman Biggs, Algebraic graph theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR 1271140
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, DOI 10.2307/1967597
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
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, DOI 10.1016/j.ejc.2008.01.022
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/.
Martin Kochol, Polynomials associated with nowhere-zero flows, J. Combin. Theory Ser. B 84 (2002), no. 2, 260–269. MR 1889258, DOI 10.1006/jctb.2001.2081
Martin Kochol, Tension polynomials of graphs, J. Graph Theory 40 (2002), no. 3, 137–146. MR 1905130, DOI 10.1002/jgt.10038
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
László Lovász, Discrete analytic functions: an exposition, Surveys in differential geometry. Vol. IX, Surv. Differ. Geom., vol. 9, Int. Press, Somerville, MA, 2004, pp. 241–273. MR 2195410, DOI 10.4310/SDG.2004.v9.n1.a7
Paolo M. Soardi, Potential theory on infinite networks, Lecture Notes in Mathematics, vol. 1590, Springer-Verlag, Berlin, 1994. MR 1324344, DOI 10.1007/BFb0073995
Richard P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171–178. MR 317988, DOI 10.1016/0012-365X(73)90108-8
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, DOI 10.1017/CBO9780511805967
Hassler Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), no. 8, 572–579. MR 1562461, DOI 10.1090/S0002-9904-1932-05460-X