{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:30:41Z","timestamp":1774369841313,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2015,12,26]],"date-time":"2015-12-26T00:00:00Z","timestamp":1451088000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Government of Russian Federation","award":["11.G34.31.00357"],"award-info":[{"award-number":["11.G34.31.00357"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s11590-015-0985-1","type":"journal-article","created":{"date-parts":[[2015,12,26]],"date-time":"2015-12-26T02:40:43Z","timestamp":1451097643000},"page":"1593-1612","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Critical hereditary graph classes: a survey"],"prefix":"10.1007","volume":"10","author":[{"given":"D. S.","family":"Malyshev","sequence":"first","affiliation":[]},{"given":"P. M.","family":"Pardalos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,26]]},"reference":[{"key":"985_CR1","doi-asserted-by":"crossref","unstructured":"Abou Eisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B.: A dichotomy for upper domination in monogenic classes. Lect. Notes Comput. Sci. 8881, 258\u2013267 (2014)","DOI":"10.1007\/978-3-319-12691-3_20"},{"key":"985_CR2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0166-218X(03)00387-1","volume":"132","author":"V Alekseev","year":"2003","unstructured":"Alekseev, V.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Appl. Math. 132, 17\u201326 (2003)","journal-title":"Discrete Appl. Math."},{"key":"985_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0166-218X(02)00290-1","volume":"135","author":"V Alekseev","year":"2004","unstructured":"Alekseev, V.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135, 3\u201316 (2004)","journal-title":"Discrete Appl. Math."},{"key":"985_CR4","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.tcs.2007.09.013","volume":"389","author":"V Alekseev","year":"2007","unstructured":"Alekseev, V., Boliac, R., Korobitsyn, D., Lozin, V.: NP-hard graph problems and boundary classes of graphs. Theor. Comput. Sci. 389, 219\u2013236 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"985_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.disc.2004.04.010","volume":"285","author":"V Alekseev","year":"2004","unstructured":"Alekseev, V., Korobitsyn, D., Lozin, V.: Boundary classes of graphs for the dominating set problem. Discrete Math. 285, 1\u20136 (2004)","journal-title":"Discrete Math."},{"key":"985_CR6","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/978-3-540-85238-4_7","volume":"5162","author":"V Alekseev","year":"2008","unstructured":"Alekseev, V., Lozin, V., Malyshev, D., Milanic, M.: The maximum independent set problem in planar graphs. Lect. Notes Comput. Sci. 5162, 96\u2013107 (2008)","journal-title":"Lect. Notes Comput. Sci."},{"key":"985_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1134\/S1990478909010013","volume":"3","author":"V Alekseev","year":"2009","unstructured":"Alekseev, V., Malyshev, D.: Planar graph classes with the independent set problem solvable in polynomial time. J. Appl. Ind. Math. 3, 1\u20134 (2009)","journal-title":"J. Appl. Ind. Math."},{"key":"985_CR8","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/3-540-36136-7_5","volume":"2518","author":"R Boliac","year":"2002","unstructured":"Boliac, R., Lozin, V.: On the clique-width of graphs in hereditary classes. Lect. Notes Comput. Sci. 2518, 44\u201354 (2002)","journal-title":"Lect. Notes Comput. Sci."},{"key":"985_CR9","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.tcs.2011.10.005","volume":"414","author":"H Broersma","year":"2012","unstructured":"Broersma, H., Golovach, P., Paulusma, D., Song, J.: Updating the complexity status of coloring graphs without a fixed induced linear forest. Theor. Comput. Sci. 414, 9\u201319 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"985_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"985_CR11","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"985_CR12","doi-asserted-by":"crossref","first-page":"1198","DOI":"10.1016\/j.dam.2005.11.005","volume":"154","author":"D Dereniowski","year":"2006","unstructured":"Dereniowski, D.: Edge ranking of weighted trees. Discrete Appl. Math. 154, 1198\u20131209 (2006)","journal-title":"Discrete Appl. Math."},{"key":"985_CR13","first-page":"97","volume":"86","author":"D Dereniowski","year":"2008","unstructured":"Dereniowski, D.: The complexity of list ranking of trees. Ars Comb. 86, 97\u2013114 (2008)","journal-title":"Ars Comb."},{"key":"985_CR14","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and intractability: a guide to the theory of NP-completeness. Freeman and Company, San Francisco (1979)"},{"key":"985_CR15","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.dam.2013.10.010","volume":"166","author":"P Golovach","year":"2014","unstructured":"Golovach, P., Paulusma, D.: List coloring in the absence of two subgraphs. Discrete Appl. Math. 166, 123\u2013130 (2014)","journal-title":"Discrete Appl. Math."},{"key":"985_CR16","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.dam.2012.08.022","volume":"161","author":"P Golovach","year":"2013","unstructured":"Golovach, P., Paulusma, D., Song, J.: $$4$$ 4 -coloring $$H$$ H -free graphs when $$H$$ H is small. Discrete Appl. Math. 161, 140\u2013150 (2013)","journal-title":"Discrete Appl. Math."},{"key":"985_CR17","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718\u2013780 (1981)","journal-title":"SIAM J. Comput."},{"key":"985_CR18","first-page":"191","volume":"2","author":"D Korobitsyn","year":"1992","unstructured":"Korobitsyn, D.: On the complexity of domination number determination in monogenic classes of graphs. Discrete Math. Appl. 2, 191\u2013199 (1992)","journal-title":"Discrete Math. Appl."},{"key":"985_CR19","doi-asserted-by":"crossref","first-page":"3544","DOI":"10.1016\/j.tcs.2011.03.001","volume":"412","author":"N Korpelainen","year":"2011","unstructured":"Korpelainen, N., Lozin, V., Malyshev, D., Tiskin, A.: Boundary properties of graphs for algorithmic graph problems. Theor. Comput. Sci. 412, 3544\u20133554 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"985_CR20","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1007\/s11083-012-9272-2","volume":"30","author":"N Korpelainen","year":"2013","unstructured":"Korpelainen, N., Lozin, V., Razgon, I.: Boundary properties of well-quasi-ordered sets of graphs. Order 30, 723\u2013735 (2013)","journal-title":"Order"},{"key":"985_CR21","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in $$P_5$$ P 5 -free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"985_CR22","doi-asserted-by":"publisher","unstructured":"Lozin, V., Malyshev, D.: Vertex coloring of graphs with few obstructions. Discrete Appl. Math. (2015). doi: 10.1016\/j.dam.2015.02.015","DOI":"10.1016\/j.dam.2015.02.015"},{"key":"985_CR23","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.jda.2014.08.005","volume":"31","author":"V Lozin","year":"2015","unstructured":"Lozin, V., Monnot, J., Ries, B.: On the maximum independent set problem in subclasses of subcubic graphs. J. Discrete Algorithms 31, 104\u2013112 (2015)","journal-title":"J. Discrete Algorithms"},{"key":"985_CR24","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.dam.2004.07.006","volume":"146","author":"V Lozin","year":"2004","unstructured":"Lozin, V., Mosca, R.: Independent sets in extensions of $$2K_2$$ 2 K 2 -free graphs. Discrete Appl. Math. 146, 74\u201380 (2004)","journal-title":"Discrete Appl. Math."},{"key":"985_CR25","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/j.ipl.2013.01.022","volume":"113","author":"V Lozin","year":"2013","unstructured":"Lozin, V., Purcell, C.: Boundary properties of the satisfiability problems. Inf. Process. Lett. 113, 313\u2013317 (2013)","journal-title":"Inf. Process. Lett."},{"key":"985_CR26","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1137\/S0895480102419755","volume":"18","author":"V Lozin","year":"2004","unstructured":"Lozin, V., Rautenbach, D.: On the band-, tree- and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18, 195\u2013206 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"985_CR27","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/jgt.21799","volume":"78","author":"V Lozin","year":"2014","unstructured":"Lozin, V., Zamaraev, V.: Boundary properties of factorial classes of graphs. J. Graph Theory 78, 207\u2013218 (2014)","journal-title":"J. Graph Theory"},{"key":"985_CR28","unstructured":"Lozin, V.: Graph theory notes. https:\/\/homepages.warwick.ac.uk\/~masgax\/Graph-Theory-notes . Accessed 11 September 2015 (2015)"},{"key":"985_CR29","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/3-540-36136-7_38","volume":"2518","author":"M Makino","year":"2002","unstructured":"Makino, M., Uno, Y., Ibaraki, T.: Minimum edge ranking spanning trees of threshold graphs. Lect. Notes Comput. Sci. 2518, 428\u2013440 (2002)","journal-title":"Lect. Notes Comput. Sci."},{"key":"985_CR30","first-page":"41","volume":"16","author":"D Malyshev","year":"2009","unstructured":"Malyshev, D.: Continued sets of boundary classes of graphs for colorability problems. Diskretnyi Analiz i Issledovanie Operatsii 16, 41\u201351 (2009). [in Russian]","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii"},{"key":"985_CR31","first-page":"43","volume":"16","author":"D Malyshev","year":"2009","unstructured":"Malyshev, D.: On minimal hard classes of graphs. Diskretnyi Analiz i Issledovanie Operatsii 16, 43\u201351 (2009). [in Russian]","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii"},{"key":"985_CR32","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1134\/S1990478910020109","volume":"4","author":"D Malyshev","year":"2010","unstructured":"Malyshev, D.: On the infinity of the set of boundary classes for the edge 3-colorability problem. J. Appl. Ind. Math. 4, 213\u2013217 (2010)","journal-title":"J. Appl. Ind. Math."},{"key":"985_CR33","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1515\/dma.2011.038","volume":"21","author":"D Malyshev","year":"2011","unstructured":"Malyshev, D.: On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number. Discrete Math. Appl. 21, 645\u2013649 (2011)","journal-title":"Discrete Math. Appl."},{"key":"985_CR34","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1134\/S1990478913020117","volume":"7","author":"D Malyshev","year":"2013","unstructured":"Malyshev, D.: A study of the boundary graph classes for colorability problems. J. Appl. Ind. Math. 7, 221\u2013228 (2013)","journal-title":"J. Appl. Ind. Math."},{"key":"985_CR35","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1134\/S199047891304008X","volume":"7","author":"D Malyshev","year":"2013","unstructured":"Malyshev, D.: Classes of subcubic planar graphs for which the independent set problem is polynomially solvable. J. Appl. Ind. Math. 7, 537\u2013548 (2013)","journal-title":"J. Appl. Ind. Math."},{"key":"985_CR36","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1134\/S1990478914020112","volume":"8","author":"D Malyshev","year":"2014","unstructured":"Malyshev, D.: Classes of graphs critical for the edge list-ranking problem. J. Appl. Ind. Math. 8, 245\u2013255 (2014)","journal-title":"J. Appl. Ind. Math."},{"key":"985_CR37","first-page":"811","volume":"11","author":"D Malyshev","year":"2014","unstructured":"Malyshev, D.: The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices. Sib. Electron. Math. Rep. 11, 811\u2013822 (2014)","journal-title":"Sib. Electron. Math. Rep."},{"key":"985_CR38","doi-asserted-by":"crossref","first-page":"2261","DOI":"10.1007\/s11590-014-0733-y","volume":"8","author":"D Malyshev","year":"2014","unstructured":"Malyshev, D.: The coloring problem for classes with two small obstructions. Optim. Lett. 8, 2261\u20132270 (2014)","journal-title":"Optim. Lett."},{"key":"985_CR39","doi-asserted-by":"publisher","unstructured":"Malyshev, D.: A complexity dichotomy and a new boundary class for the dominating set problem. J. Comb. Optim. (2015). doi: 10.1007\/s10878-015-9872-z","DOI":"10.1007\/s10878-015-9872-z"},{"key":"985_CR40","unstructured":"Malyshev, D.: A complexity dichotomy for the dominating set problem. (2015). arXiv:1506.00202"},{"key":"985_CR41","doi-asserted-by":"crossref","first-page":"1860","DOI":"10.1016\/j.disc.2015.04.019","volume":"338","author":"D Malyshev","year":"2015","unstructured":"Malyshev, D.: The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs. Discrete Math. 338, 1860\u20131865 (2015)","journal-title":"Discrete Math."},{"key":"985_CR42","doi-asserted-by":"publisher","unstructured":"Malyshev, D.: Two cases of polynomial-time solvability for the coloring problem. J. Comb. Optim. (2015). doi: 10.1007\/s10878-014-9792-3","DOI":"10.1007\/s10878-014-9792-3"},{"key":"985_CR43","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0166-218X(92)90041-8","volume":"35","author":"O Murphy","year":"1992","unstructured":"Murphy, O.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35, 167\u2013170 (1992)","journal-title":"Discrete Appl. Math."},{"key":"985_CR44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C Papadimitriou","year":"1993","unstructured":"Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"985_CR45","unstructured":"De Ridder, N., et al.: Information system on graph classes and their inclusions. (2015). http:\/\/www.graphclasses.org . Accessed 21 June 2015"},{"key":"985_CR46","unstructured":"Schweitzer, P.: Towards an isomorphism dichotomy for hereditary graph classes. (2014). arXiv:1411.1977"},{"key":"985_CR47","first-page":"1","volume":"17","author":"A Shen","year":"2002","unstructured":"Shen, A., Vereshchagin, N.: Basic set theory. Am. Math. Soc. 17, 1\u2013130 (2002)","journal-title":"Basic set theory. Am. Math. Soc."},{"key":"985_CR48","first-page":"281","volume":"21","author":"S Whitesides","year":"1984","unstructured":"Whitesides, S.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. Ann. Discrete Math. 21, 281\u2013297 (1984)","journal-title":"Ann. Discrete Math."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-015-0985-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-015-0985-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-015-0985-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-015-0985-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T23:41:58Z","timestamp":1567467718000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-015-0985-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,26]]},"references-count":48,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["985"],"URL":"https:\/\/doi.org\/10.1007\/s11590-015-0985-1","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,26]]}}}