Abstract:
This paper describes polynomial-time algorithm which tests isomorphism of undirected graphs uncontracted to Bipartite complete graph $K_{3,g}$. The algorithm may be applied for graphs of bounded valence and for graphs with bounded genus within the same time. Construction of algorithm is based on properties of colour graphs from above class and on results of L. Babai and E. Luks about canonical forms for graphs.