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

Zap. Nauchn. Sem. LOMI, 1988 Volume 174, Pages 147–177 (Mi znsl4516)

This article is cited in 32 papers

Isomorphism problem for classes of graphs closed under contractions

I. N. Ponomarenko


Abstract: A graph $G$ is contracted to graph $H$ if $H$ can be obtained from an induced subgraph of $G$ by contracting edged. The main purpose of the paper is to describe $C$-classes, i.e. classes of graphs closed under the contractions, from the point of view isomorphism problem. The key part of the considerations is connected to constructing polynomial-time algorithm to test isomorphism of graphs with bounded Hadviger number. The algorithm involves combinatorial properties of graphs from above class and group-theoretical ones of their automorphism groups. The result about graphs with bounded Hadviger number gives opportunity to characterise both isomorphism-complete $C$-classes and $C$-classes with polynomial-time isomorphism test.

UDC: 519.5


 English version:
Journal of Soviet Mathematics, 1991, 55:2, 1621–1643

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025