MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Motivated by Khovanov's categorification of the Jones polynomial, several authors have worked on the categorification of graph invariants. For the chromatic polynomial some references are:

"A categorification for the chromatic polynomial" by L. Helme-Guizon, Y. Rong

"The chromatic polynomial of fatgraphs and its categorification" by M. Loebl, I. Moffatt

The main defining property for the chromatic polynomial is the deletion-contraction recurrence $$\chi_{G}(x)=\chi_{G\backslash e}(x)-\chi_{G/e}(x)$$ Where $G/e$ is the graph obtained by contracting the edge $e$, and $G\backslash e$ is the graph obtained by deleting $e$. These categorifications usually associate objects $A(G)$ to graphs in such a way that this relation categorifies to an exact sequence $$A(G)\to A(G/e)\to A(G\backslash e).$$

Similarly one can define a polynomial $\bar\chi_G(n)$ which counts the number of colorings of $G$ with $n$ colors so that $n-1$ colors are distributed properly (no two adjacent vertices get the same color among these) and the last color can be distributed arbitrarily. This polynomial satisfies $$\bar\chi_G(x)=\bar\chi_{G\backslash e}(x)-\bar\chi_{G/e}(x)+\bar\chi_{G\dagger e}(x)$$ where $G\dagger e$ is the extraction of the edge $e$, which means we remove $e$ together with its two vertices from $G$.

Is there is a similar categorification of this polynomial in the literature?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.