{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:32:05Z","timestamp":1774369925906,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100009409","name":"Russian Science Support Foundation","doi-asserted-by":"publisher","award":["19-71-00005"],"award-info":[{"award-number":["19-71-00005"]}],"id":[{"id":"10.13039\/100009409","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s11590-020-01593-0","type":"journal-article","created":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T05:02:46Z","timestamp":1590210166000},"page":"137-152","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The computational complexity of weighted vertex coloring for $$\\{P_5,K_{2,3},K^+_{2,3}\\}$$-free graphs"],"prefix":"10.1007","volume":"15","author":[{"given":"D. S.","family":"Malyshev","sequence":"first","affiliation":[]},{"given":"O. O.","family":"Razvenskaya","sequence":"additional","affiliation":[]},{"given":"P. M.","family":"Pardalos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,23]]},"reference":[{"key":"1593_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22499","author":"K Cameron","year":"2019","unstructured":"Cameron, K., Huang, S., Penev, I., Sivaraman, V.: The class of $$(P_7, C_4, C_5)$$- free graphs: decomposition, algorithms, and $$\\chi $$-boundedness. J. Graph Theory (2019). https:\/\/doi.org\/10.1002\/jgt.22499","journal-title":"J. Graph Theory"},{"key":"1593_CR2","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/j.disc.2017.09.013","volume":"341","author":"K Cameron","year":"2018","unstructured":"Cameron, K., da Silva, M., Huang, S., Vuskovic, K.: Structure and algorithms for $$(cap, even~hole)$$-free graphs. Discrete Math. 341, 463\u2013473 (2018)","journal-title":"Discrete Math."},{"key":"1593_CR3","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/j.jcss.2017.06.005","volume":"89","author":"K Dabrowski","year":"2017","unstructured":"Dabrowski, K., Dross, F., Paulusma, D.: Colouring diamond-free graphs. J. Comput. Syst. Sci. 89, 410\u2013431 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"1593_CR4","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2013.12.004","volume":"522","author":"K Dabrowski","year":"2014","unstructured":"Dabrowski, K., Golovach, P., Paulusma, D.: Colouring of graphs with Ramsey-type forbidden subgraphs. Theor. Comput. Sci. 522, 34\u201343 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"1593_CR5","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1016\/j.disc.2011.12.012","volume":"312","author":"K Dabrowski","year":"2012","unstructured":"Dabrowski, K., Lozin, V., Raman, R., Ries, B.: Colouring vertices of triangle-free graphs without forests. Discrete Math. 312, 1372\u20131385 (2012)","journal-title":"Discrete Math."},{"key":"1593_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.ipl.2018.02.003","volume":"134","author":"K Dabrowski","year":"2018","unstructured":"Dabrowski, K., Paulusma, D.: On colouring $$(2P_2, H)$$-free and $$(P_5, H)$$-free graphs. Inf. Process. Lett. 134, 35\u201341 (2018)","journal-title":"Inf. Process. Lett."},{"key":"1593_CR7","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.entcs.2019.08.033","volume":"346","author":"Y Dai","year":"2019","unstructured":"Dai, Y., Foley, A., Ho\u00e0ng, C.: On coloring a class of claw-free graphs: to the memory of Fr\u00e9d\u00e9ric Maffray. Electron. Notes Theor. Comput. Sci. 346, 369\u2013377 (2019)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"1593_CR8","unstructured":"Foley, A., Fraser, D., Ho\u00e0ng, C., Holmes, K., LaMantia, T.: The intersection of two vertex coloring problems. arXiv:1904.08180"},{"key":"1593_CR9","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.dam.2016.08.016","volume":"231","author":"D Fraser","year":"2017","unstructured":"Fraser, D., Hamela, A., Ho\u00e0ng, C., Holmes, K., LaMantia, T.: Characterizations of $$(4K_1, C_4, C_5)$$-free graphs. Discrete Appl. Math. 231, 166\u2013174 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR10","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.jcss.2019.06.002","volume":"106","author":"S Gaspers","year":"2019","unstructured":"Gaspers, S., Huang, S., Paulusma, D.: Colouring square-free graphs without long induced paths. J. Comput. Syst. Sci. 106, 60\u201379 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"1593_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"P Golovach","year":"2017","unstructured":"Golovach, P., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of coloring graphs with forbidden subgraphs. J. Graph Theory 84, 331\u2013363 (2017)","journal-title":"J. Graph Theory"},{"key":"1593_CR12","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.dam.2014.08.008","volume":"180","author":"P Golovach","year":"2015","unstructured":"Golovach, P., Paulusma, D., Ries, B.: Coloring graphs characterized by a forbidden subgraph. Discrete Appl. Math. 180, 101\u2013110 (2015)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.dam.2015.10.024","volume":"216","author":"P Hell","year":"2017","unstructured":"Hell, P., Huang, S.: Complexity of coloring graphs without paths and cycles. Discrete Appl. Math. 216, 211\u2013232 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR14","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.dam.2015.01.022","volume":"186","author":"C Ho\u00e0ng","year":"2015","unstructured":"Ho\u00e0ng, C., Lazzarato, D.: Polynomial-time algorithms for minimum weighted colorings of $$(P_5,\\overline{P_5})$$-free graphs and similar graph classes. Discrete Appl. Math. 186, 106\u2013111 (2015)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR15","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1007\/s00453-018-0457-y","volume":"81","author":"T Karthick","year":"2017","unstructured":"Karthick, T., Maffray, F., Pastor, L.: Polynomial cases for the vertex coloring problem. Algorithmica 81, 1053\u20131074 (2017)","journal-title":"Algorithmica"},{"key":"1593_CR16","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-45477-2_23","volume":"2204","author":"D Kr\u00e1l\u2019","year":"2001","unstructured":"Kr\u00e1l\u2019, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.: Complexity of coloring graphs without forbidden induced subgraphs. Lect. Notes Comput. Sci. 2204, 254\u2013262 (2001)","journal-title":"Lect. Notes Comput. Sci."},{"key":"1593_CR17","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/S0166-218X(99)00249-8","volume":"103","author":"D Kim","year":"2000","unstructured":"Kim, D., Du, D.-Z., Pardalos, P.M.: A coloring problem on the $$n$$-cube. Discrete Appl. Math. 103, 307\u2013311 (2000)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR18","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.dam.2015.02.015","volume":"216","author":"V Lozin","year":"2017","unstructured":"Lozin, V., Malyshev, D.: Vertex coloring of graphs with few obstructions. Discrete Appl. Math. 216, 273\u2013280 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR19","doi-asserted-by":"publisher","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":"1593_CR20","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s10878-014-9792-3","volume":"31","author":"D Malyshev","year":"2016","unstructured":"Malyshev, D.: Two cases of polynomial-time solvability for the coloring problem. J. Comb. Optim. 31, 833\u2013845 (2016)","journal-title":"J. Comb. Optim."},{"key":"1593_CR21","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1007\/s10878-016-0008-x","volume":"33","author":"D Malyshev","year":"2017","unstructured":"Malyshev, D.: Polynomial-time approximation algorithms for the coloring problem in some cases. J. Comb. Optim. 33, 809\u2013813 (2017)","journal-title":"J. Comb. Optim."},{"key":"1593_CR22","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.dam.2018.04.006","volume":"247","author":"D Malyshev","year":"2018","unstructured":"Malyshev, D.: The weighted coloring problem for two graph classes characterized by small forbidden induced structures. Discrete Appl. Math. 247, 423\u2013432 (2018)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR23","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.dam.2016.10.025","volume":"219","author":"D Malyshev","year":"2017","unstructured":"Malyshev, D., Lobanova, O.: Two complexity results for the vertex coloring problem. Discrete Appl. Math. 219, 158\u2013166 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1593_CR24","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1007\/978-1-4613-0303-9_16","volume-title":"Handbook of Combinatorial Optimization","author":"PM Pardalos","year":"1998","unstructured":"Pardalos, P.M., Mavridou, T., Xue, J.: The graph coloring problem: a bibliographic survey. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 1077\u20131141. Springer, Boston (1998)"},{"key":"1593_CR25","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s10878-018-00376-9","volume":"38","author":"H Wang","year":"2019","unstructured":"Wang, H., Pardalos, P.M., Liu, B.: Optimal channel assignment with list-edge coloring. J. Combin. Optim. 38, 197\u2013207 (2019)","journal-title":"J. Combin. Optim."},{"key":"1593_CR26","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1007\/s10898-013-0138-y","volume":"60","author":"H Wang","year":"2014","unstructured":"Wang, H., Wu, L., Wu, W., Pardalos, P.M., Wu, J.: Minimum total coloring of planar graph. J. Glob. Optim. 60, 777\u2013791 (2014)","journal-title":"J. Glob. Optim."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01593-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-020-01593-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01593-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T23:47:58Z","timestamp":1621727278000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-020-01593-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,23]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["1593"],"URL":"https:\/\/doi.org\/10.1007\/s11590-020-01593-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,23]]},"assertion":[{"value":"5 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}