On distinguishing trees by their chromatic symmetric functions

Let T be an unrooted tree. The chromatic symmetric functionXT, introduced by Stanley, is a sum of monomial symmetric functions corresponding to proper colorings of T. The subtree polynomialST, 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 ST=〈Φ,XT〉, where 〈⋅,⋅〉 is the Hall inner product on symmetric functions and Φ 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 (spiders and some caterpillars), and one family of unicyclic graphs (squids) whose members are determined completely by their chromatic symmetric functions.