Nowhereharmonic colorings of graphs
Authors:
Matthias Beck and Benjamin Braun
Journal:
Proc. Amer. Math. Soc. 140 (2012), 4763
MSC (2010):
Primary 05C78; Secondary 05A15, 52B20, 52C35
Published electronically:
May 9, 2011
MathSciNet review:
2833516
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Proper vertex colorings of a graph are related to its boundary map , also called its signed vertexedge incidence matrix. The vertex Laplacian of a graph, , a natural extension of the boundary map, leads us to introduce nowhereharmonic 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 nowhereharmonic 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. Integerpoint enumeration
in polyhedra. MR
2271992 (2007h:11119)
 2.
Matthias
Beck and Thomas
Zaslavsky, Insideout polytopes, Adv. Math.
205 (2006), no. 1, 134–162. MR 2254310
(2007e:52017), 10.1016/j.aim.2005.07.006
 3.
Matthias
Beck and Thomas
Zaslavsky, The number of nowherezero flows on graphs and signed
graphs, J. Combin. Theory Ser. B 96 (2006),
no. 6, 901–918. MR 2274083
(2007k:05084), 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
(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. 14, 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/s0020901007826
 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
(2009i:05102), 10.1016/j.ejc.2008.01.022
 8.
Andrew Van Herick, Theoretical and computational methods for lattice point enumeration in insideout 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 nowherezero flows, J.
Combin. Theory Ser. B 84 (2002), no. 2,
260–269. MR 1889258
(2002k:05193), 10.1006/jctb.2001.2081
 10.
Martin
Kochol, Tension polynomials of graphs, J. Graph Theory
40 (2002), no. 3, 137–146. MR 1905130
(2003f:05048), 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 (2010g:05021)
 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), 10.4310/SDG.2004.v9.n1.a7
 13.
Paolo
M. Soardi, Potential theory on infinite networks, Lecture
Notes in Mathematics, vol. 1590, SpringerVerlag, 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.
Richard
P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge
Studies in Advanced Mathematics, vol. 49, Cambridge University Press,
Cambridge, 1997. With a foreword by GianCarlo 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, 10.1090/S00029904193205460X
 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, Insideout polytopes, Adv. Math. 205 (2006), no. 1, 134162. MR 2254310 (2007e:52017)
 3.
 , The number of nowherezero flows on graphs and signed graphs, J. Combin. Theory Ser. B 96 (2006), no. 6, 901918. 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. 14, 4246. 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/s0020901007826
 7.
 Beifang Chen and Jue Wang, The flow and tension spaces and lattices of signed graphs, European J. Combin. 30 (2009), no. 1, 263279. MR 2460231
 8.
 Andrew Van Herick, Theoretical and computational methods for lattice point enumeration in insideout 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 nowherezero flows, J. Combin. Theory Ser. B 84 (2002), no. 2, 260269. MR 1889258 (2002k:05193)
 10.
 , Tension polynomials of graphs, J. Graph Theory 40 (2002), no. 3, 137146. 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. 241273. MR 2195410 (2007g:30067)
 13.
 Paolo M. Soardi, Potential theory on infinite networks, Lecture Notes in Mathematics, vol. 1590, SpringerVerlag, Berlin, 1994. MR 1324344 (96i:31005)
 14.
 Richard P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171178. 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 GianCarlo 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, 572579. 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
Email:
beck@math.sfsu.edu
Benjamin Braun
Affiliation:
Department of Mathematics, University of Kentucky, Lexington, Kentucky 405060027
Email:
benjamin.braun@uky.edu
DOI:
http://dx.doi.org/10.1090/S000299392011108797
PII:
S 00029939(2011)108797
Keywords:
Nowhereharmonic coloring,
chromatic polynomial,
boundary map,
graph Laplacian,
insideout 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 DMS0810105 (first author) and DMS0758321 (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.
