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