|MIT Combinatorics Seminar
Is a tree determined by its chromatic symmetric function?
(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.