A criterion for a class of graphs to be a boundary class and applications

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.