Polynomial isomorphism algorithm for graphs which do not pinch to K3,g

In this paper we construct a polynomial algorithm for verifying the isomorphism of graphs which do not pinch to K_3,g. In the construction we use properties of colored graphs from this class and results of Babai-Luks on canonization of graphs. The class cited contains the class of graphs of genus not exceeding g, and we apply the algorithm constructed to the recognition of isomorphism of graphs of bounded valence. The method given is a generalization of the combinatorial and group-theoretic approach to the isomorphism problem.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 99–114, 1984.