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.