Acyclic Orientations and the Chromatic Polynomial of Signed Graphs

Abstract

We present a new correspondence between acyclic orientations and coloring of a signed graph (symmetric graph). Goodall et al. introduced a bivariate chromatic polynomial ${\chi }_G(k,l)$ that counts the number of signed colorings using colors $0,\pm 1,\dots ,\pm k$ along with $l-1$ symmetric colors $0_1,\dots ,0_{l-1}$. We show that the evaluation of the bivariate chromatic polynomial $|{\chi }_G(-1,2)|$ is equal to the number of acyclic orientations of the signed graph modulo the equivalence relation generated by swapping sources and sinks. We present three proofs of this fact, a proof using toric hyperplane arrangements, a proof using deletion-contraction, and a direct proof.

17 pages, 7 figures