Volume 15, No 6, 2008, P. 3-10

UDC 519.178
V. E. Alekseev, D. S. Malyshev
A criterion for a class of graphs to be a boundary class and applications

Abstract:
A new definition of the boundary class of graphs is given and the corresponding criterion is proved. The class of all graphs in which every connected component is a tree with at most three leaves is considered as an example. This class is known to be the boundary class for several graph problems. We establish some sufficient conditions for this class to be a boundary class and prove that it is the boundary class for the bipartite subgraph and the planar subgraph problems. 
Bibl. 8. 

Keywords: computational complexity, boundary class, maximum subgraph problem.

Alekseev Vladimir Evgen’evich ¹
Malyshev Dmitry Sergeevich ¹
1. Gorky State University,
23 Gagarin ave., 2 building, 603950 N. Novgorod, Russia
e-mail: ave@uic.nnov.ru