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

Jake Huryn, Oscar Coppola, Michael Reilly

Publication date: 12 February 2023

Abstract: In 1995, Richard 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.

This page was built for publication: An Extension of Stanley's Symmetric Acyclicity Theorem to Signed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426235)