A categorification for the chromatic polynomial
  For each graph we construct graded cohomology groups whose graded Euler characteristic is the chromatic polynomial of the graph. We show the cohomology groups satisfy a long exact sequence which corresponds to the well-known deletion-contraction rule. This work is motivated by Khovanov's work on categorification of the Jones polynomial of knots. 
Laure Helme-Guizon, Yongwu Rong