|
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
Posted:
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 (2007h:11119)
- 2.
Matthias
Beck and Thomas
Zaslavsky, Inside-out polytopes, Adv. Math.
205 (2006), no. 1, 134–162. MR 2254310
(2007e:52017), http://dx.doi.org/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
(2007k:05084), http://dx.doi.org/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. 1-4, 42–46. MR
1502436, http://dx.doi.org/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
(2009i:05102), http://dx.doi.org/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
(2002k:05193), http://dx.doi.org/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), http://dx.doi.org/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)
- 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.
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
(98a:05001)
- 16.
Hassler
Whitney, A logical expansion in
mathematics, Bull. Amer. Math. Soc.
38 (1932), no. 8,
572–579. MR
1562461, http://dx.doi.org/10.1090/S0002-9904-1932-05460-X
- 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
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 40506-0027
Email:
benjamin.braun@uky.edu
DOI:
http://dx.doi.org/10.1090/S0002-9939-2011-10879-7
PII:
S 0002-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
Posted:
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.
|
