A categorification of the chromatic symmetric function

The Stanley chromatic symmetric function X_G of a graph G is a symmetric function generalization of the chromatic polynomial and has interesting combinatorial properties. We apply the ideas from Khovanov homology to construct a homology theory of graded S_n-modules, whose graded Frobenius series Frob_G(q,t) specializes to the chromatic symmetric function at q=t=1. This homology theory can be thought of as a categorification of the chromatic symmetric function, and it satisfies homological analogues of several familiar properties of X_G. In particular, the decomposition formula for X_G discovered recently by Orellana, Scott, and independently by Guay-Paquet, is lifted to a long exact sequence in homology.