A Signed Graph Analogue of Acyclic Orientation Polynomials and the Sink Theorem
The Electronic Journal of Combinatorics · 13.03.2026 · 33 (1)
DOI: 10.37236/14450 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 13.03.2026. Verfasst von Kang-Ju Lee.
Abstract (Originalsprache)
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.
Zitieren
APA
Lee, K. (2026). A Signed Graph Analogue of Acyclic Orientation Polynomials and the Sink Theorem. The Electronic Journal of Combinatorics, 33(1). https://doi.org/10.37236/14450
Vancouver
Lee K. A Signed Graph Analogue of Acyclic Orientation Polynomials and the Sink Theorem. The Electronic Journal of Combinatorics. 2026;33(1). doi:10.37236/14450
BibTeX
@article{Lee2026,
author = {Lee, Kang-Ju},
title = {A Signed Graph Analogue of Acyclic Orientation Polynomials and the Sink Theorem},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {1},
doi = {10.37236/14450}
}
EUVIMED