Isomorphism problem for classes of graphs closed under contractions
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 147-177
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{ZNSL_1988_174_a6,
author = {I. N. Ponomarenko},
title = {Isomorphism problem for classes of graphs closed under contractions},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {147--177},
publisher = {mathdoc},
volume = {174},
year = {1988},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a6/}
}
I. N. Ponomarenko. Isomorphism problem for classes of graphs closed under contractions. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 147-177. http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a6/