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

Zap. Nauchn. Sem. LOMI, 1984 Volume 137, Pages 99–114 (Mi znsl4789)

Polynomial isomorphism algorithm for graphs which are not contracted to $K_{3,g}$.

I. N. Ponomarenko


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.

UDC: 519.5



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025