EUVIMEDOpdag EUVIMED
Crossref

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

Kang-Ju Lee

The Electronic Journal of Combinatorics · 2026-03-13 · 33 (1)

DOI: 10.37236/14450 ↗

At a glance

Journal article in The Electronic Journal of Combinatorics, published online on 2026-03-13. Written by Kang-Ju Lee.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →