
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
Abstract:
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 wellknown 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.
Keywords:
extremal graph problems, computational complexity, boundary class.
Full text:
PDF file (653 kB)
References:
PDF file
HTML file
Bibliographic databases:
UDC:
519.178 Received: 20.10.2008 Revised: 09.02.2009
Citation:
D. S. Malyshev, “Boundary classes of graphs for some recognition problems”, Diskretn. Anal. Issled. Oper., 16:2 (2009), 85–94
Citation in format AMSBIB
\Bibitem{Mal09}
\by D.~S.~Malyshev
\paper Boundary classes of graphs for some recognition problems
\jour Diskretn. Anal. Issled. Oper.
\yr 2009
\vol 16
\issue 2
\pages 8594
\mathnet{http://mi.mathnet.ru/da570}
\mathscinet{http://www.ams.org/mathscinetgetitem?mr=2574311}
\zmath{https://zbmath.org/?q=an:1249.05367}
Linking options:
http://mi.mathnet.ru/eng/da570 http://mi.mathnet.ru/eng/da/v16/i2/p85
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
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 3colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. elektron. matem. izv., 11 (2014), 811–822

Number of views: 
This page:  311  Full text:  67  References:  21  First page:  8 
