The Chromatic Symmetric Function for Unicyclic Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912688057090048 |
|---|---|
| author | Bingham, Aram Johnston, Lisa Lawson, Colin Orellana, Rosa Pan, Jianping Sato, Chelsea |
| author_facet | Bingham, Aram Johnston, Lisa Lawson, Colin Orellana, Rosa Pan, Jianping Sato, Chelsea |
| contents | 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 $\textit{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_06486 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Chromatic Symmetric Function for Unicyclic Graphs Bingham, Aram Johnston, Lisa Lawson, Colin Orellana, Rosa Pan, Jianping Sato, Chelsea Combinatorics 05E05, 05C60 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 $\textit{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. |
| title | The Chromatic Symmetric Function for Unicyclic Graphs |
| topic | Combinatorics 05E05, 05C60 |
| url | https://arxiv.org/abs/2505.06486 |