AN ELEMENTARY CHROMATIC REDUCTION FOR GAIN GRAPHS AND SPECIAL HYPERPLANE ARRANGEMENTS

Abstract. A gain graph is a graph whose edges are labelled invertibly by gains from a group. A weak chromatic function of gain graphs with gains in a fixed group satisfies two laws: deletion-contraction for links with neutral gain, 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 two 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 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 or new proofs of the zero-free chromatic polynomial and the integral and modular chromatic functions of these gain graphs, hence the characteristic polynomials and hypercubical latticepoint 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 covers of the graph of (−1)-gain edges. We also show how to calculate the total chromatic polynomial of any gain graph and especially of the Catalan, Shi, and Linial gain graphs. 1