{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:25:40Z","timestamp":1759667140444,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T00:00:00Z","timestamp":1556236800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1550991"],"award-info":[{"award-number":["DMS-1550991"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-16-1-0404"],"award-info":[{"award-number":["W911NF-16-1-0404"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1140766","1180830"],"award-info":[{"award-number":["1140766","1180830"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Millennium Nucleus Information and Coordination in Networks","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]},{"name":"CMM-Basal","award":["AFB 170001"],"award-info":[{"award-number":["AFB 170001"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00453-019-00577-6","type":"journal-article","created":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T01:47:31Z","timestamp":1556329651000},"page":"3186-3199","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximately Coloring Graphs Without Long Induced Paths"],"prefix":"10.1007","volume":"81","author":[{"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2536-5618","authenticated-orcid":false,"given":"Sophie","family":"Spirkl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maya","family":"Stein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingxian","family":"Zhong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,26]]},"reference":[{"key":"577_CR1","unstructured":"Brakensiek, J., Guruswami, V.: New hardness results for graph and hypergraph colorings. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"577_CR2","doi-asserted-by":"crossref","unstructured":"Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.: Three-coloring and list three-coloring graphs without induced paths on seven vertices. Combinatorica 38(4), 779\u2013801 (2018)","DOI":"10.1007\/s00493-017-3553-8"},{"key":"577_CR3","doi-asserted-by":"crossref","unstructured":"Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: 48th Annual IEEE Symposium on Foundations of Computer Science (2007)","DOI":"10.1109\/FOCS.2007.72"},{"key":"577_CR4","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. I. Extending an excellent precoloring. arXiv preprint \n                    arXiv:1802.02282\n                    \n                   (2018)"},{"key":"577_CR5","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. II. Finding an excellent precoloring. arXiv preprint \n                    arXiv:1802.02283\n                    \n                   (2018)"},{"key":"577_CR6","unstructured":"Chuzhoy, J.: Private communication (2015)"},{"key":"577_CR7","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1137\/07068062X","volume":"39","author":"I Dinur","year":"2009","unstructured":"Dinur, I., Mossel, E., Regev, O.: Conditional hardness for approximate coloring. SIAM J. Comput. 39, 843\u2013873 (2009)","journal-title":"SIAM J. Comput."},{"key":"577_CR8","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(86)90184-2","volume":"43","author":"K Edwards","year":"1986","unstructured":"Edwards, K.: The complexity of colouring problems on dense graphs. Theor. Comput. Sci. 43, 337\u2013343 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"577_CR9","first-page":"125","volume":"26","author":"P Erd\u0151s","year":"1979","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. Congressus Numerantium 26, 125\u2013157 (1979)","journal-title":"Congressus Numerantium"},{"key":"577_CR10","volume-title":"A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: A Guide to the Theory of NP-Completeness. WH Freemann, New York (1979)"},{"key":"577_CR11","doi-asserted-by":"crossref","unstructured":"Groenland, C., Okrasa, K., Rz\u0105\u017cewski, P., Scott, A., Seymour, P., Spirkl, S.: $$ H $$-colouring $$ P_t $$-free graphs in subexponential time. arXiv preprint \n                    arXiv:1803.05396\n                    \n                   (2018)","DOI":"10.1016\/j.dam.2019.04.010"},{"issue":"4","key":"577_CR12","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs. J. Graph Theory 84(4), 331\u2013363 (2017)","journal-title":"J. Graph Theory"},{"issue":"3\u20134","key":"577_CR13","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Appl. Math. 19(3\u20134), 413\u2013441 (1987)","journal-title":"Appl. Math."},{"issue":"1","key":"577_CR14","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"CT Ho\u00e0ng","year":"2010","unstructured":"Ho\u00e0ng, C.T., Kami\u0144ski, M., Lozin, V., Sawada, J., Shu, X.: Deciding $$k$$-colorability of $$P_5$$-free graphs in polynomial time. Algorithmica 57(1), 74\u201381 (2010)","journal-title":"Algorithmica"},{"key":"577_CR15","doi-asserted-by":"publisher","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\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"577_CR16","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."},{"issue":"11","key":"577_CR17","doi-asserted-by":"publisher","first-page":"3074","DOI":"10.1093\/comjnl\/bxv039","volume":"58","author":"S Huang","year":"2015","unstructured":"Huang, S., Johnson, M., Paulusma, D.: Narrowing the complexity gap for colouring $$(C_s, P_t)$$-free graphs. Comput. J. 58(11), 3074\u20133088 (2015)","journal-title":"Comput. J."},{"key":"577_CR18","first-page":"61","volume":"2","author":"M Kami\u0144ski","year":"2007","unstructured":"Kami\u0144ski, M., Lozin, V.: Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math. 2, 61\u201366 (2007)","journal-title":"Contrib. Discrete Math."},{"key":"577_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"577_CR20","series-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume-title":"Coloring 3-Colorable Graphs with $$o (n^{1\/5})$$ Colors","author":"K Kawarabayashi","year":"2014","unstructured":"Kawarabayashi, K., Thorup, M.: Coloring 3-Colorable Graphs with $$o (n^{1\/5})$$ Colors. LIPIcs-Leibniz International Proceedings in Informatics, vol. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern (2014)"},{"key":"577_CR21","first-page":"254","volume":"2001","author":"D Kr\u00e1l","year":"2001","unstructured":"Kr\u00e1l, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. Proc. WG 2001, 254\u2013262 (2001)","journal-title":"Proc. WG"},{"key":"577_CR22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D Leven","year":"1983","unstructured":"Leven, D., Galil, Z.: NP-completeness of finding the chromatic index of regular graphs. J. Algorithms 4, 35\u201344 (1983)","journal-title":"J. Algorithms"},{"issue":"3","key":"577_CR23","first-page":"3","volume":"29","author":"VG Vizing","year":"1976","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. Diskret. Analiz 29(3), 3\u201310 (1976)","journal-title":"Diskret. Analiz"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00577-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00577-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00577-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:34:36Z","timestamp":1589697276000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00577-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,26]]},"references-count":23,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["577"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00577-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,4,26]]},"assertion":[{"value":"28 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}