A Signed Graph Analogue of Acyclic Orientation Polynomials and the Sink Theorem

Abstract

We introduce the acyclic orientation polynomial of a signed graph, defined as the generating function that counts sinks of its acyclic orientations, thereby refining the number of acyclic orientations. We prove that our acyclic orientation polynomial satisfies the deletion–contraction recurrence with the recurrence rule depending on the sign of the edge involved. Using this recurrence, we expand the polynomial in terms of its subgraphs as an analogue of the expansion of the chromatic polynomial. The main application is an alternative proof of the signed graph analogue of Stanley's sink theorem for chromatic symmetric functions, which does not rely on a signed version of quasi-symmetric functions and $P$-partitions.