Computational verification that the chromatic symmetric function determines up to isomorphism trees of order at most 23.

Introduced by Richard Stanley, the chromatic symmetric function is a generalization of the chromatic polynomial of a graph [1]. Stanley defines the chromatic symmetric function as a sum of monomial symmetric functions corresponding to proper colorings. He asked whether the chromatic symmetric function distinguishes non-isomorphic trees, and mentioned [2] that T. Chow has checked it to be true for trees with at most 9 vertices. This problem remains open. It should be noted that there exists non-isomorphic graphs (on 5 vertices) with the same chromatic symmetric function.

We have verified computationally that the chromatic symmetric function X(T) determines T up to isomorphism for all trees T of order at most 23. Our program checks for equality between chromatic symmetric functions by considering the the expansion X(T) in terms of monomial symmetric functions. The program is implemented in Java, and its size currently stands at 2000 lines of code.

To generate all free trees of a given size, we use a constant amortized algorithm described in [3]. Implentations of the Li-Rusky algorithm in C can be found on the Combinatorial Object Server (COS). For cases 22 and 23, we utilize results of Jeremy Martin and Jennifer Wagner, described in [4], to reduce the search space considerably. It should be noted also that the incorporation of Martin et. al.'s results have led to marked improvements in running times of smaller cases as well.

The computational efficiency of our program has benefited significantly from the algorithms and work described above, and also that of others not mentioned here. The presence of any errors in the code, however, is of course the sole responsiblity of its implementor Li-Yang Tan.

Related Work

It is mentioned in Enumerative Combinatorics that T. Chow has checked this for trees of size at most 9. Martin and Wagner have checked this for trees of order at most 14, using a database of trees available online, generated by Piece, Malarz, and Kulakowski.

In [5], Dohmen et. al. present a two-variable generalization of the chromatic polynomial, with which they use to verify computationally that there are no non-isomorphic trees of order at most 15 vertices with the same chromatic symmetric function.

More Information

Please contact Li-Yang Tan for more information.

References

[1] Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math. 111 (1995), 166-194.
[2] Richard P. Stanley, Enumerative Combinatorics, Volume 2. Cambridge University Press, Cambridge, 1997.
[3] G. Li and F. Ruskey, The Advantages of Forward Thinking in Genearating Rooted and Free Trees, ACM-SIAM Symposium on Discrete Algorithms 1999.
[4] Jeremy L. Martin, Matthew Morin and Jennifer D. Wagner, On the chromatic symmetric function of a tree, In preparation.
[5] K. Dohmen, A. Pönitz, P. Tittmann, A new two-variable generalization of the chromatic polynomial, Discrete Mathematics and Theoretical Computer Science 6, 2003, 069-090.
[6] Bruce E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Springer GTM, 2001
Li-Yang Tan
lytan AT wustl DOT edu