Acyclic Orientations and the Chromatic Polynomial of Signed Graphs

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 $\mathrm{\mid }{\chi }_G(-1,2)\mathrm{\mid }$ 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.