On distinguishing trees by their chromatic symmetric functions
Preprint
Abstract
Let $T$ be an unrooted tree. The \emph{chromatic symmetric function} $X_T$, introduced by Stanley, is a sum of monomial symmetric functions corresponding to proper colorings of $T$. The \emph{subtree polynomial} $S_T$, first considered under a different name by Chaudhary and Gordon, is the bivariate generating function for subtrees of $T$ by their numbers of edges and leaves. We prove that $S_T = <\Phi,X_T>$, where $<\cdot,\cdot>$ is the Hall inner product on symmetric functions and $\Phi$ is a certain symmetric function that does not depend on $T$. Thus the chromatic symmetric function is a stronger isomorphism invariant than the subtree polynomial. As a corollary, the path and degree sequences of a tree can be obtained from its chromatic symmetric function. As another application, we exhibit two infinite families of trees (\emph{spiders} and some \emph{caterpillars}), and one family of unicyclic graphs (\emph{squids}) whose members are determined completely by their chromatic symmetric functions.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Non-isomorphic caterpillars with identical subtree dataDiscrete Mathematics, 2006
- A Chromatic Symmetric Function in Noncommuting VariablesJournal of Algebraic Combinatorics, 2001
- Trees with the same degree sequence and path numbersDiscrete Mathematics, 1995
- A Symmetric Function Generalization of the Chromatic Polynomial of a GraphAdvances in Mathematics, 1995
- Brick tabloids and the connection matrices between bases of symmetric functionsDiscrete Applied Mathematics, 1991
- Tutte polynomials for treesJournal of Graph Theory, 1991
- Caterpillars, ribbons, and the chromatic symmetric function
- The Reconstruction of a Tree from its Maximal SubtreesCanadian Journal of Mathematics, 1966