Combinatorics Seminar: "Multivariate chromatic polynomials for rooted graphs"

Abstract: Richard Stanley defined the chromatic symmetric function X_G of a graph G and conjectured that trees T and U are isomorphic if and only if X_T=X_U. In the first part of this talk we use Eisenstein's Criterion to show that the chromatic symmetric functions for trees are irreducible over Q[x1,...,xN]. In the second part we introduce a variation of the chromatic symmetric function for rooted graphs, where we require the root vertex to have a specified color. Our polynomials satisfy the analogue of Stanley's conjecture: two rooted trees are isomorphic as rooted graphs if and only if their rooted chromatic polynomials are equal. This can be proved via unique factorization or directly via algebraic transformations to pointed chromatic functions and rooted U-polynomials. In addition to sketching these arguments, we explore some of the combinatorial properties of these polynomials. This talk is based on joint work with Nick Loehr.

Host: Nathan Lesnevich