The Chromatic Symmetric Function for Unicyclic Graphs
The Electronic Journal of Combinatorics · 17.07.2026 · 33 (3)
DOI: 10.37236/15119 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 17.07.2026. Verfasst von Aram Bingham und 5 weiteren Autor:innen.
Abstract (Originalsprache)
Motivated by the question of which structural properties of a graph can be recovered from the chromatic symmetric function (CSF), we study the CSF of connected unicyclic graphs. While it is known that there can be non-isomorphic unicyclic graphs with the same CSF, we find experimentally that such examples are rare for graphs with up to 17 vertices. In fact, in many cases we can recover data such as the number of leaves, number of internal edges, cycle size, and number of attached non-trivial trees, by extending known results for trees to unicyclic graphs. These results are obtained by analyzing the CSF of a connected unicyclic graph in the star-basis using the deletion-near-contraction (DNC) relation developed by Aliste-Prieto, Orellana and Zamora, and computing the "leading" partition, its coefficient, as well as coefficients indexed by hook partitions. We also give explicit formulas for star-expansions of several classes of graphs, developing methods for extracting coefficients using structural properties of the graph.
Zitieren
APA
Bingham, A., Johnston, L., Lawson, C., Orellana, R., Pan, J., & Sato, C. (2026). The Chromatic Symmetric Function for Unicyclic Graphs. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/15119
Vancouver
Bingham A, Johnston L, Lawson C, Orellana R, Pan J, Sato C. The Chromatic Symmetric Function for Unicyclic Graphs. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/15119
BibTeX
@article{Bingham2026,
author = {Bingham, Aram and Johnston, Lisa and Lawson, Colin and Orellana, Rosa and Pan, Jianping and Sato, Chelsea},
title = {The Chromatic Symmetric Function for Unicyclic Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {3},
doi = {10.37236/15119}
}
EUVIMED