A note on distinguishing trees with the chromatic symmetric function (Q2666579)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on distinguishing trees with the chromatic symmetric function |
scientific article |
Statements
A note on distinguishing trees with the chromatic symmetric function (English)
0 references
23 November 2021
0 references
The paper studies which parameters of a tree can be recovered from certain well-studied polynomial functions associated to it. For a tree \(T\), define its trunk \(T^\circ\) to be the smallest subtree of \(T\) which contains all its vertices with degree three or more. After removing \(T^\circ\) from \(T\) we are left with a set of edge-disjoint paths each with an endpoint in \(T^\circ\), we say those are the twigs of \(T\). The author shows that the bivariate subtree polynomial (as defined by \textit{S. Chaudhary} and \textit{G. Gordon} [J. Graph Theory 15, No. 3, 317--331 (1991; Zbl 0737.05041)]) of \(T\) determines the size of \(T^\circ\), and also the length of all the twigs of \(T\). As a corollary, the chromatic symmetric function of \(T\) (as defined by \textit{R. P. Stanley} [Adv. Math. 111, No. 1, 166--194 (1995; Zbl 0831.05027)]) also determines the same parameters.
0 references
chromatic symmetric function
0 references
tree isomorphism conjecture
0 references
subtree polynomial
0 references
algebraic combinatorics
0 references
graph polynomials
0 references
0 references
0 references