Two reductions of graph isomorphism to problems for polynomials
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VIII, Tome 88 (1979), pp. 56-61
Voir la notice de l'article provenant de la source Math-Net.Ru
The problem of isomorphism of $n$-vertices graphs with weights on their edges possesses a full system of invariants which consists of $(n^2+1)$ polynomials of degree $\leq n^2$ (theorem 1). The proof of existence of such a system is not effective and is based on the primitive element theorem. Theorem 2 asserts that the graph isomorphism problem (or even the problem of divising the set of vertices of a graph $T$ on the domains of transitivity) can be reduced in polynomial time to the problem of decomposition of some univariable polynomial $f$ into irreducible multipliers over some field $F_T$ (the coefficients of $f$ depend only on
the number of vertices of $T$).
@article{ZNSL_1979_88_a3,
author = {D. Yu. Grigor'ev},
title = {Two reductions of graph isomorphism to problems for polynomials},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {56--61},
publisher = {mathdoc},
volume = {88},
year = {1979},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1979_88_a3/}
}
D. Yu. Grigor'ev. Two reductions of graph isomorphism to problems for polynomials. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VIII, Tome 88 (1979), pp. 56-61. http://geodesic.mathdoc.fr/item/ZNSL_1979_88_a3/