An elementary chromatic reduction for gain graphs and special hyperplane arrangements

zbMATH Open1188.05076arXiv1001.4216MaRDI QIDQ2380285FDOQ2380285

Authors: Pascal Berthomé, Raul Cordovil, Véronique Ventos, Thomas Zaslavsky, David Forge 

Publication date: 26 March 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A gain graph is a graph whose edges are labelled invertibly by "gains" from a group. "Switching" is a transformation of gain graphs that generalizes conjugation in a group. A "weak chromatic function" of gain graphs with gains in a fixed group satisfies three laws: deletion-contraction for links with neutral gain, invariance under switching, and nullity on graphs with a neutral loop. The laws lead to the "weak chromatic group" of gain graphs, which is the universal domain for weak chromatic functions. We find expressions, valid in that group, for a gain graph in terms of minors without neutral-gain edges, or with added complete neutral-gain subgraphs, that generalize the expression of an ordinary chromatic polynomial in terms of monomials or falling factorials. These expressions imply relations for chromatic functions of gain graphs. We apply our relations to some special integral gain graphs including those that correspond to the Shi, Linial, and Catalan arrangements, thereby obtaining new evaluations of and new ways to calculate the zero-free chromatic polynomial and the integral and modular chromatic functions of these gain graphs, hence the characteristic polynomials and hypercubical lattice-point counting functions of the arrangements. We also calculate the total chromatic polynomial of any gain graph and especially of the Catalan, Shi, and Linial gain graphs.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Totally frustrated states in the chromatic theory of gain graphs
• A symmetric function generalization of the chromatic polynomial of a graph
• Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs
• Burnside chromatic polynomials of group-invariant graphs
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs

zbMATH Keywords

chromatic polynomialswitchinggain graphweak chromatic functionweak chromatic group of gain graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Cited In (6)

• Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs
• Burnside chromatic polynomials of group-invariant graphs
• Coloring permutation-gain graphs
• Totally frustrated states in the chromatic theory of gain graphs
• Gessel polynomials, rooks, and extended linial arrangements
• Matroids of gain signed graphs

This page was built for publication: An elementary chromatic reduction for gain graphs and special hyperplane arrangements

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