On distinguishing trees by their chromatic symmetric functions

Details On distinguishing trees by their chromatic symmetric functions On distinguishing trees by their chromatic symmetric functions

2006-09-12

arxiv.org/abs/math/0609339v3

J. Combin. Theory Ser. A 115 (2008), pp. 237-253

Mathematics

Combinatorics

16 pages, 3 figures. Added references [2], [13], and [15]

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On distinguishing trees by their chromatic symmetric functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On distinguishing trees by their chromatic symmetric functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On distinguishing trees by their chromatic symmetric functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-554761