An Extension of Stanley's Symmetric Acyclicity Theorem to Signed Graphs

Abstract

In 1995, Richard P. Stanley introduced the chromatic symmetric function $X_G$ of a graph $G$ and proved that, when written in terms of the elementary symmetric functions, it reveals the number of acyclic orientations of $G$ with a given number of sinks. In this paper, we generalize this result to signed graphs, that is, to graphs whose edges are labeled with $+$ or $-$ and whose colorings and orientations can interact with their signs.

Additionally, we introduce a non-homogeneous basis which detects the number of sinks and which not only gives a Stanley-type result for signed graphs, but gives an analogous result of this form for unsigned graphs as well.