Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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.