A categorification of the chromatic symmetric polynomial

Abstract

The Stanley chromatic polynomial of a graph $G$ is a symmetric function generalization of the chromatic polynomial, and has interesting combinatorial properties. We apply the ideas of Khovanov homology to construct a homology $H$*($G$) of graded $S_n$-modules, whose graded Frobenius series $Frob_G(q,t)$ reduces to the chromatic symmetric function at $q=t=1$. We also obtain analogues of several familiar properties of the chromatic symmetric polynomials in terms of homology.

Keywords

• symmetric functions
• chromatic polynomial
• khovanov homology
• $s_n$-modules
• frobenius series
• graph colouring
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]