{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T20:44:40Z","timestamp":1725914680052},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319687049"},{"type":"electronic","value":"9783319687056"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_15","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T06:06:22Z","timestamp":1509516382000},"page":"193-205","source":"Crossref","is-referenced-by-count":0,"title":["Approximately Coloring Graphs Without Long Induced Paths"],"prefix":"10.1007","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"}]},{"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":[[2017,11,2]]},"reference":[{"key":"15_CR1","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 (FOCS 2007) (2007)","DOI":"10.1109\/FOCS.2007.72"},{"key":"15_CR2","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 (2015, preprint)"},{"key":"15_CR3","unstructured":"Chuzhoy, J.: Private communication"},{"key":"15_CR4","doi-asserted-by":"crossref","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":"15_CR5","doi-asserted-by":"crossref","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":"15_CR6","first-page":"125","volume":"26","author":"P Erd\u0151s","year":"1979","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. Congr. Numer. 26, 125\u2013157 (1979)","journal-title":"Congr. Numer."},{"key":"15_CR7","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. W.H. Freemann, New York (1979)"},{"key":"15_CR8","doi-asserted-by":"publisher","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: Survey on the computational complexity of colouring graphs with forbidden subgraphs. J. Graph Theory (to appear). doi: 10.1002\/jgt.22028","DOI":"10.1002\/jgt.22028"},{"issue":"3\u20134","key":"15_CR9","doi-asserted-by":"crossref","first-page":"413","DOI":"10.4064\/am-19-3-4-413-441","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Applicationes Mathematicae 19(3\u20134), 413\u2013441 (1987)","journal-title":"Applicationes Mathematicae"},{"issue":"1","key":"15_CR10","doi-asserted-by":"crossref","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$$ k -colorability of $$P_5$$ P 5 -free graphs in polynomial time. Algorithmica 57(1), 74\u201381 (2010)","journal-title":"Algorithmica"},{"key":"15_CR11","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\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"15_CR12","doi-asserted-by":"crossref","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$$ k -coloring $$P_t$$ P t -free graphs. Eur. J. Comb. 51, 336\u2013346 (2016)","journal-title":"Eur. J. Comb."},{"key":"15_CR13","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. Discret. Math. 2, 61\u201366 (2007)","journal-title":"Contrib. Discret. Math."},{"key":"15_CR14","doi-asserted-by":"crossref","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":"15_CR15","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.-I., Thorup, M.: Coloring 3-colorable graphs with $$o (n^{1\/5})$$ o ( n 1 \/ 5 ) colors. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)","DOI":"10.1145\/3001582"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-45477-2_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D Kr\u00e1l\u2019","year":"2001","unstructured":"Kr\u00e1l\u2019, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 254\u2013262. Springer, Heidelberg (2001). doi: 10.1007\/3-540-45477-2_23"},{"key":"15_CR17","doi-asserted-by":"crossref","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":"15_CR18","first-page":"10","volume":"29","author":"VG Vizing","year":"1976","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. Diskret. Analiz 29(3), 10 (1976)","journal-title":"Diskret. Analiz"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T22:53:11Z","timestamp":1603234391000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}