Some algebraic methods for calculation of the number of colorings of a graph

Yu. V. Matiyasevich

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part VI, Tome 283 (2001), pp. 193-205

Résumé

With an arbitrary graph $G$ having $n$ vertices and $m$ edges, and with an arbitrary natural number $p$, we associate in a natural way a polynomial $R(x_1,\dots,x_2)$ with integer coefficients such that the number of colorings of the vertices of the graph $G$ in $p$ colors is equal to $p^{m-n}R(0,\dots,0)$. Also with an arbitrary maximal plannar graph $G$ we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph $G$ in 3 colors can be calculated in a several ways from the coefficients of each of these polynomials.