{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T18:56:11Z","timestamp":1774378571490,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T00:00:00Z","timestamp":1596067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T00:00:00Z","timestamp":1596067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/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\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-16-1-0404"],"award-info":[{"award-number":["W911NF-16-1-0404"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11801284"],"award-info":[{"award-number":["11801284"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00453-020-00754-y","type":"journal-article","created":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T12:02:36Z","timestamp":1596110556000},"page":"216-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["List 3-Coloring Graphs with No Induced $$P_6+rP_3$$"],"prefix":"10.1007","volume":"83","author":[{"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[]},{"given":"Shenwei","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Sophie","family":"Spirkl","sequence":"additional","affiliation":[]},{"given":"Mingxian","family":"Zhong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,30]]},"reference":[{"key":"754_CR1","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.ic.2014.02.004","volume":"237","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Closing complexity gaps for coloring problems on $$H$$-free graphs. Inf. Comput. 237, 204\u2013214 (2014)","journal-title":"Inf. Comput."},{"key":"754_CR2","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":"754_CR3","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 graphs without induced paths on seven vertices. Combinatorica 38, 779\u2013801 (2018)","journal-title":"Combinatorica"},{"key":"754_CR4","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":"754_CR5","unstructured":"Klimo\u0161ov\u00e1, T., Malik, J., Masa\u0159\u00edk, T., Novotn\u00e1, J., Paulusma, D., Sl\u00edvov\u00e1, V.: Colouring $$(P_r+P_s)$$-free graphs. arXiv:1804.11091"},{"key":"754_CR6","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, 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":"754_CR7","unstructured":"Groenland, C., Okrasa, K., Rz\u0105\u017cewski, P., Scott, A., Seymour, P., Spirkl, S.: $$H$$-coloring $$P_t$$-free graphs in subexponential time. arXiv:1803.05396"},{"key":"754_CR8","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., 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":"754_CR9","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. Theoret. Comput. Sci. 43, 337\u2013343 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"754_CR10","unstructured":"Stacho, J.: Private communication"},{"key":"754_CR11","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01305948","volume":"14","author":"G Ding","year":"1994","unstructured":"Ding, G., Seymour, P., Winkler, P.: Bounding the vertex cover number of a hypergraph. Combinatorica 14, 23\u201334 (1994)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00754-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00754-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00754-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T23:33:01Z","timestamp":1627601581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00754-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,30]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["754"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00754-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,30]]},"assertion":[{"value":"16 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}