Séminaire Lotharingien de Combinatoire, 93B.78 (2025), 11 pp.
Michael Gonzalez, Rosa Orellana and Mario Tomba
On the Reconstruction of Trees from their Chromatic Symmetric Functions
Abstract.
We study Stanley's chromatic symmetric function (CSF) for trees when expressed in the star basis. We use the deletion-near-contraction (DNC) algorithm by Aliste-Prieto et al. to compute coefficients that occur in the CSF in the star basis. In particular, one of our main results determines the smallest partition in lexicographic order that occurs as an indexing partition in the CSF, and we also give a formula for its coefficient. In addition to describing properties of trees encoded in the coefficients of the star basis, we give an algorithm for reconstructing trees of diameter less than six.
Received: November 15, 2024.
Accepted: February 15, 2025.
Final version: April 1, 2025.
The following versions are available: