An elementary chromatic reduction for gain graphs and special hyperplane arrangements

Pascal Berthomé ; Raul Cordovil ; David Forge ; Véronique Ventos ; Thomas Zaslavsky

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

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 are analogous to those of the chromatic polynomial of an ordinary graph, though they are different from those usually assumed of gain graphs or matroids. The three 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 all switching-invariant functions of gain graphs, such as chromatic polynomials, that satisfy the deletion-contraction identity for neutral links and are zero on graphs with neutral loops. Examples are the total chromatic polynomial of any gain graph, including its specialization the zero-free chromatic polynomial, and the integral and modular chromatic functions of an integral gain graph. 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. The proof involves gain graphs between the Catalan and Shi graphs whose polynomials are expressed in terms of descending-path vertex partitions of the graph of $(-1)$-gain edges. We also calculate the total chromatic polynomial of any gain graph and especially of the Catalan, Shi, and Linial gain graphs.

Détail

DOI : 10.37236/210

Classification : 05C22, 05C15, 05C78, 52C35
Mots-clés : gain graph, switching, weak chromatic function, weak chromatic group of gain graphs, chromatic polynomial