Volume 16, No 2, 2009, P. 85-94
D. S. Malyshev
Boundary classes of graphs for some recognition problems
The class of all graphs in which every connected component is a tree with at most three leaves and the class of line graphs of this class are considered in the article. There is a series of well-known problems for which these classes are boundary classes.We study common properties of such problems. Namely, we prove a sufficient condition for the considered classes to be boundary classes. Using the obtained tool we add 8 new cases of given classes being boundary classes to known ones.
Keywords: extremal graph problems, computational complexity, boundary class.
Malyshev Dmitry Sergeevich 1
1. Nizhegorodskiy State University,
23 Gagarin ave., building 2, 603950 N. Novgorod, Russia