ENRU
English version: 

Volume 23, No 1, 2016, P. 516 UDC 519.17
Keywords: graph, independent set, forbidden subtree, polynomial algorithm. DOI: 10.17377/daio.2016.23.499 Vladimir E. Alekseev ^{1} Received 11 June 2015 References[1] V. E. Alekseev, A polynomial algorithm for finding the largest independent sets in clawfree graphs, Diskretn. Anal. Issled. Oper., Ser. 1, 6, No. 4, 3–19, 1999.[2] V. E. Alekseev and D. V. Zakharova, Independent sets in the graphs with bounded minors of the extended incidence matrix, Diskretn. Anal. Issled. Oper., 17, No. 1, 3–10, 2010. Translated in J. Appl. Ind. Math., 5, No. 1, 14–18, 2011. [3] V. E. Alekseev and D. V. Korobitsyn, Complexity of some problems on hereditary classes of graphs, Diskretn. Mat., 4, No. 4, 34–40, 1992. [4] V. E. Alekseev and D. S. Malyshev, Planar graph classes with the independent set problem solvable in polynomial time, Diskretn. Anal. Issled. Oper., 15, No. 1, 3–10, 2008. Translated in J. Appl. Ind. Math., 3, No. 1, 1–4, 2009. [5] V. E. Alekseev and V. A. Talanov, Grafy i algoritmy. Struktury dannykh. Modeli vychislenii (Graphs and Algorithms. Data Structures. Computation Models), InternetUniv. Inform. Tekhnol., BINOM. Lab. Znanii, Moscow, 2006. [6] A. V. Bankevich and D. V. Karpov, Bounds of the number of leaves of spanning trees, Zap. Nauchn. Semin. POMI, 391, 18–34, 2011. Translated in J. Math. Sci., New York, 184, No. 5, 564–572, 2012. [7] D. V. Zakharova, Weighted independent sets in graphs with bounded minors of the extended incidence matrix, in Materialy X Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya” (Proc. X Int. Seminar “Discrete Math. and Its Applications”), Moscow, Russia, Jan. 1–6, 2010, pp. 303–305, Izd. Mekh.Mat. Fak. MGU, Moscow, 2010. [8] D. S. Malyshev, Classes of subcubic planar graphs for which the independent set problem is polynomially solvable, Diskretn. Anal. Issled. Oper., 20, No. 3, 26–44, 2013. Translated in J. Appl. Ind. Math., 7, No. 4, 537–548, 2013. [9] V. N. Shevchenko, Kachestvennye voprosy tselochislennogo programmirovaniya (Qualitative Problems in Integer Programming), Nauka, Moscow, 1995. [10] P. Erdõs and G. Szekeres, A combinatorial problem in geometry, Compos. Math., 2, 463–470, 1935. [11] G. J. Minty, On maximal independent sets of vertices in clawfree graphs, J. Comb. Theory, Ser. B, 28, 284–304, 1980. [12] N. Sbihi, Algorithme de recherche d’un stable de cardinalit´e maximum dans un graphe sans ´etoile, Discrete Math., 29, No. 1, 53–76, 1980. 

© Sobolev Institute of Mathematics, 2015  