{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:32:09Z","timestamp":1774369929678,"version":"3.50.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s11590-022-01859-9","type":"journal-article","created":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T04:45:09Z","timestamp":1645764309000},"page":"1403-1409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An intractability result for the vertex 3-colourability problem"],"prefix":"10.1007","volume":"16","author":[{"given":"D. S.","family":"Malyshev","sequence":"first","affiliation":[]},{"given":"O. V.","family":"Pristavchenko","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,25]]},"reference":[{"key":"1859_CR1","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/s00493-017-3553-8","volume":"38","author":"F Bonomo","year":"2018","unstructured":"Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.: Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica 38, 779\u2013801 (2018)","journal-title":"Combinatorica"},{"key":"1859_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2011.10.005","volume":"414","author":"HJ Broersma","year":"2012","unstructured":"Broersma, H.J., Golovach, P.A., Paulusma, D., Song, J.: Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoret. Comput. Sci. 414, 9\u201319 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"1859_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discret. Math. 30, 289\u2013293 (1980)","journal-title":"Discret. Math."},{"key":"1859_CR4","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Co., New York (1979)"},{"key":"1859_CR5","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.dam.2012.08.022","volume":"161","author":"PA Golovach","year":"2013","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: 4-coloring $$H$$-free graphs when $$H$$ is small. Discret. Appl. Math. 161, 140\u2013150 (2013)","journal-title":"Discret. Appl. Math."},{"key":"1859_CR6","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. Discret. Appl. Math. 180, 101\u2013110 (2015)","journal-title":"Discret. Appl. Math."},{"key":"1859_CR7","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":"1859_CR8","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. Discret. Appl. Math. 216, 211\u2013232 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1859_CR9","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"C Ho\u00e0ng","year":"2010","unstructured":"Ho\u00e0ng, C., Kami\u0144ski, M., Lozin, V.V., Sawada, J., Shu, X.: $$k$$-colorability of $$P_5$$-free graphs in polynomial time. Algorithmica 57, 74\u201381 (2010)","journal-title":"Algorithmica"},{"key":"1859_CR10","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.ejc.2015.06.005","volume":"51","author":"S Huang","year":"2016","unstructured":"Huang, S.: Improved complexity results on $$k$$-coloring $$P_t$$-free graphs. Eur. J. Comb. 51, 336\u2013346 (2016)","journal-title":"Eur. J. Comb."},{"key":"1859_CR11","doi-asserted-by":"publisher","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. Discret. Math. 338, 1860\u20131865 (2015)","journal-title":"Discret. Math."},{"key":"1859_CR12","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1007\/s00373-017-1790-7","volume":"33","author":"D Malyshev","year":"2017","unstructured":"Malyshev, D.: The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs. Graphs Comb. 33, 1009\u20131022 (2017)","journal-title":"Graphs Comb."},{"key":"1859_CR13","doi-asserted-by":"publisher","first-page":"38","DOI":"10.15507\/2079-6900.22.202001.38-47","volume":"22","author":"D Malyshev","year":"2020","unstructured":"Malyshev, D.: A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions. Zhurnal Srednevolzhskogo matematicheskogo obshchestva 22, 38\u201347 (2020). ((in Russian))","journal-title":"Zhurnal Srednevolzhskogo matematicheskogo obshchestva"},{"key":"1859_CR14","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1134\/S1990478918040166","volume":"25","author":"D Sirotkin","year":"2018","unstructured":"Sirotkin, D., Malyshev, D.: On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size. J. Appl. Ind. Math. 25, 759\u2013769 (2018)","journal-title":"J. Appl. Ind. Math."},{"key":"1859_CR15","doi-asserted-by":"crossref","unstructured":"Spirkl, S., Chudnovsky, M., Zhong, M.: Four-coloring $$P_6$$-free graphs. In: Simposium on discrete algorithims, pp. 1239\u20131256 (2019)","DOI":"10.1137\/1.9781611975482.76"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01859-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01859-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01859-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T16:19:01Z","timestamp":1652199541000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01859-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["1859"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01859-9","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,25]]},"assertion":[{"value":"11 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}