Nowhere-harmonic colorings of graphs

DOI10.1090/S0002-9939-2011-10879-7MaRDI QIDQ5388783zbMATH OpenFDO

Authors Matthias Beck, Benjamin Braun

Publication date 20 April 2012

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.1272

zbMATH Keywords

boundary mapchromatic polynomialgraph Laplacianhyperplane arrangementinside-out polytopenowhere-harmonic coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

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 some examples demonstrating that nowhere-harmonic colorings are more complicated from an enumerative perspective than proper colorings.

Recommendations

• Unlabeled signed graph coloring
• A bivariate chromatic polynomial for signed graphs
• The chromatic number of a signed graph
• Edge coloring signed graphs
• Enumerating colorings, tensions and flows in cell complexes

Cites work

• A logical expansion in mathematics
• Acyclic orientations of graphs
• Computing the Continuous Discretely
• Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
• scientific article; zbMATH DE number 2133156 (Why is no real title available?)
• scientific article; zbMATH DE number 5577862 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• Inside-out polytopes
• Polynomials associated with nowhere-zero flows
• Potential theory on infinite networks
• Tension polynomials of graphs
• The flow and tension spaces and lattices of signed graphs
• The number of nowhere-zero flows on graphs and signed graphs

Cited in

(4)

• Laplacian simplices
• Vertex-colored graphs, bicycle spaces and Mahler measure
• Bounds of characteristic polynomials of regular matroids
• Polynomial algorithms for canonical forms of orientations

Describes a project that uses

Uses Software

• IOP

This page was built for publication: Nowhere-harmonic colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5388783)