EUVIMEDEUVIMED entdecken
Crossref

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

Kang-Ju Lee

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →