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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references