Chromatic Symmetric Functions

In 1995, Richard Stanley introduced the chromatic symmetric function (CSF) of a graph and proposed the following problem:

Do there exist two nonisomorphic trees with the same CSF?

The problem seems to be very hard. Here is what is known:

• Stanley gave an example of two 5-vertex non-tree graphs (the bowtie and the kite) with the same CSF. By gluing together copies of this, I think you can get infinitely many pairs with the same CSF. (I've written down a construction twice and have forgotten it both times.)
• Matt Morin, Jennifer Wagner and I proved that you can recover the degree sequence of a tree from its CSF, as well as the number of vertices at each given distance. More generally, for each \(i,j\), you can recover the number of subtrees with \(i\) edges and \(j\) leaves. But that data only suffices to distinguish trees of 10 or fewer vertices.
• My student Keeler Russell carried out a brute-force search of all trees on 25 or fewer vertices and determined that they all had different CSF's. Keeler's code used the degree-sequence result mentioned above to break the problem into more feasible chunks, as well as a lot of fancy footwork with data structures (think about it: how do you efficiently represent an unlabeled tree and compute its CSF, and how do you generate all unlabeled trees? on \(n\) vertices?) Keeler's code, written in C++, is freely available either from his GitHub repository or a mirror on my website. If you have any questions about using the code, please contact Keeler:

Last updated Tue 1/7/14