{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T16:35:05Z","timestamp":1774370105193,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540427070","type":"print"},{"value":"9783540454779","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45477-2_23","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T11:09:01Z","timestamp":1187262541000},"page":"254-262","source":"Crossref","is-referenced-by-count":89,"title":["Complexity of Coloring Graphs without Forbidden Induced Subgraphs"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Kr\u00e1l\u2019","sequence":"first","affiliation":[]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,10,2]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V.: Perfectly ordered graphs, in: Topics on Perfect Graphs (C. Berge, V. Chv\u00e1tal, eds.), Annals of Discrete Mathematics 21 (1984) 63\u201365","DOI":"10.1016\/S0304-0208(08)72923-2"},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P. Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P.: Graph theory and probability, Canad. J. Math. 11 (1959) 34\u201338.","journal-title":"Canad. J. Math."},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"M.R. Fellows","year":"1995","unstructured":"Fellows, M.R., Kratochv\u00edl, J., Middendorf, M., Pfeiffer, F.: The complexity of induced minors and related problems, Algorithmica 13 (1995) 266\u2013282","journal-title":"Algorithmica"},{"key":"23_CR4","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 (1981) 718\u2013720.","journal-title":"SIAM J. Comput."},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses, SIAM J. Comput. 11 (1982) 329\u2013343.","journal-title":"SIAM J. Comput."},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0012-365X(97)89267-9","volume":"162","author":"F. Maffray","year":"1996","unstructured":"Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs, Discr. Math. 162 (1996), 313\u2013317","journal-title":"Discr. Math."},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(88)90143-3","volume":"28","author":"S. Olariu","year":"1988","unstructured":"Olariu, S.: Paw-free graphs, Inform. Process. Lett. 28 (1988), 53\u201354","journal-title":"Inform. Process. Lett."},{"key":"23_CR8","unstructured":"Randerath, B., Schiermeyer, I.: 3-colorability in P for P\n                        6-free graphs, Rutcor Research Report 39-2001, ext. abstract in Electronic Notes in Discrete Math., Vol. 8 (2001)."}],"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\/3-540-45477-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,22]],"date-time":"2019-02-22T04:00:36Z","timestamp":1550808036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45477-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540427070","9783540454779"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/3-540-45477-2_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}