This article is cited in 2 scientific papers (total in 2 papers)
Boundary classes of graphs for some recognition problems
D. S. Malyshev
Nizhegorodskiy State University, N. Novgorod, Russia
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. Bibl. 10.
extremal graph problems, computational complexity, boundary class.
PDF file (653 kB)
D. S. Malyshev, “Boundary classes of graphs for some recognition problems”, Diskretn. Anal. Issled. Oper., 16:2 (2009), 85–94
Citation in format AMSBIB
\paper Boundary classes of graphs for some recognition problems
\jour Diskretn. Anal. Issled. Oper.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Malyshev D.S., “Boundary Graph Classes for Some Maximum Induced Subgraph Problems”, J. Comb. Optim., 27:2 (2014), 345–354
D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. elektron. matem. izv., 11 (2014), 811–822
|Number of views:|