|
Zapiski Nauchnykh Seminarov POMI, 2001, Volume 283, Pages 193–205
(Mi znsl1530)
|
|
|
|
This article is cited in 9 scientific papers (total in 9 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.
Received: 25.09.2001
Citation:
Yu. V. Matiyasevich, “Some algebraic methods for calculation of the number of colorings of a graph”, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part VI, Zap. Nauchn. Sem. POMI, 283, POMI, St. Petersburg, 2001, 193–205; J. Math. Sci. (N. Y.), 121:3 (2004), 2401–2408
Linking options:
https://www.mathnet.ru/eng/znsl1530 https://www.mathnet.ru/eng/znsl/v283/p193
|
Statistics & downloads: |
Abstract page: | 509 | Full-text PDF : | 354 |
|