MIT Combinatorics Seminar

Is a tree determined by its chromatic symmetric function?

Jeremy Martin  (University of Kansas)

Friday, March 02, 2007    4:15 pm    Room 2-136


The chromatic symmetric function of a graph, first studied by Stanley in 1995, is a much stronger invariant than the chromatic polynomial, but no one seems to be sure exactly how strong it is. In particular, Stanley's question of whether two non-isomorphic trees can have the same chromatic symmetric function remains unanswered, and seems to be quite hard. Recently, Matthew Morin, Jennifer Wagner and myself have made partial progress by proving that the chromatic symmetric function is strictly stronger than Chaudhary and Gordon's subtree polynomial. We've also identified some special classes of trees which really are determined by their chromatic symmetric functions. As an unexpected bonus, studying the chromatic symmetric functions of certain trees called "caterpillars" may have applications in protein sequencing.