  Motivated by Khovanov homology and relations between the Jones polynomial and
graph polynomials, we construct a homology theory for embedded graphs from
which the chromatic polynomial can be recovered as the Euler characteristic.
For plane graphs, we show that our chromatic homology can be recovered from the
Khovanov homology of an associated link. We apply this connection with Khovanov
homology to show that the torsion-free part of our chromatic homology is
independent of the choice of planar embedding of a graph.
  We extend our construction and categorify the Bollobas-Riordan polynomial (a
generalisation of the Tutte polynomial to embedded graphs). We prove that both
our chromatic homology and the Khovanov homology of an associated link can be
recovered from this categorification.
