For all finite trees T_1 and T_2, if their chromatic symmetric functions are equal, X_T_1=X_T_2, then the trees are isomorphic, T_1 cong T_2. Here, for a finite graph G, X_G(mathbfx)=∑_kappa∏_v∈ V(G)x_kappa(v), where the sum is over all proper colorings kappa:V(G)→N; equivalently, the chromatic symmetric function distinguishes all nonisomorphic finite trees.

Stanley’s tree-isomorphism conjecture

For all finite trees $T_1$ and $T_2$ , if their chromatic symmetric functions are equal, $X_{T_1}=X_{T_2}$ , then the trees are isomorphic, $T_1\cong T_2$ . Here, for a finite graph $G$ , $X_G(\mathbf{x})=\sum_{\kappa}\prod_{v\in V(G)}x_{\kappa(v)}$ , where the sum is over all proper colorings $\kappa:V(G)\to\mathbb{N}$ ; equivalently, the chromatic symmetric function distinguishes all nonisomorphic finite trees.

Progress summary

Partially solved

The conjecture remains open, but new work proves it for broader classes of trees and leaves only difficult cases unresolved.

Stanley asked whether two trees with the same chromatic symmetric function must be isomorphic. The unrestricted conjecture remains unresolved.

Known results

Caterpillars: established in 2018 via reconstruction from the $U$ -polynomial.
Trees of diameter at most $5$ : reconstructed from their chromatic symmetric functions by an explicit algorithm (2025).
Trees with exactly two vertices of degree at least $3$ : settled affirmatively (2023).
Further classes generalizing proper caterpillars: established in 2023.

August 2026 reconstruction criterion

Zeng, Zijian established a criterion that handles repeated leaf-component orders, extending the verified range beyond earlier distinct-order conditions. The result advances reconstruction but explicitly leaves arbitrary diameter- $6$ trees and the general conjecture open.

Current status (as of August 2026): The conjecture is proved for several substantial classes, including all trees of diameter at most $5$ , but arbitrary diameter- $6$ trees and the unrestricted case remain open.

Sources

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Multiplicity-Isolated Cores and Chromatic Symmetric Reconstruction of Trees — arXiv — Zeng, Zijian

algebraic-combinatorics graph-theory

1 day ago