Minor of a graph

Материал из WikiGrapp
Перейти к:навигация, поиск

Minor of a graph --- минор графа.

A graph H obtained from G by a series of vertex deletions, edge deletions and contractions of an edge. A class of graphs {\mathcal
F} is called minor-closed if for every graph G in {\mathcal F}, every minor of G is also a member of {\mathcal F}. For a class of graphs {\mathcal F}, a finite obstruction set S is a finite set of minors such that a graph is a member of {\mathcal F} if and only if it does not contain an element of S as a minor.

The graphs in every minor-closed class of graphs are recognizable in {\mathcal O}(n^{3}) time.