RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2001 Volume 283, Pages 193–205 (Mi znsl1530)

This article is cited in 8 papers

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

Yu. V. Matiyasevich

St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences

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.

UDC: 519.17

Received: 25.09.2001


 English version:
Journal of Mathematical Sciences (New York), 2004, 121:3, 2401–2408

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024