{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T16:35:54Z","timestamp":1774974954931,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,5,29]],"date-time":"2008-05-29T00:00:00Z","timestamp":1212019200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00453-008-9197-8","type":"journal-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T15:37:31Z","timestamp":1211989051000},"page":"74-81","source":"Crossref","is-referenced-by-count":117,"title":["Deciding k-Colorability of P 5-Free Graphs in\u00a0Polynomial Time"],"prefix":"10.1007","volume":"57","author":[{"given":"Ch\u00ednh T.","family":"Ho\u00e0ng","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Kami\u0144ski","sequence":"additional","affiliation":[]},{"given":"Vadim","family":"Lozin","sequence":"additional","affiliation":[]},{"given":"Joe","family":"Sawada","sequence":"additional","affiliation":[]},{"given":"Xiao","family":"Shu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,29]]},"reference":[{"issue":"4","key":"9197_CR1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/BF02352694","volume":"21","author":"G. Bacs\u00f3","year":"1990","unstructured":"Bacs\u00f3, G., Tuza, Z.: Dominating cliques in P 5-free graphs. Period. Math. Hung. 21(4), 303\u2013308 (1990)","journal-title":"Period. Math. Hung."},{"issue":"3","key":"9197_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9197_CR3","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, electronic edn. (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"9197_CR4","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1051\/ro:2003013","volume":"37","author":"D. Werra de","year":"2003","unstructured":"de Werra, D., Kobler, D.: Graph coloring: foundations and applications. RAIRO Oper. Res. 37, 29\u201366 (2003)","journal-title":"RAIRO Oper. Res."},{"key":"9197_CR5","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S. Even","year":"1972","unstructured":"Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. Assoc. Comput. Mach. 19, 400\u2013410 (1972)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9197_CR6","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum coloring by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1, 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"9197_CR7","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0166-218X(97)00093-0","volume":"80","author":"V. Giakoumakis","year":"1997","unstructured":"Giakoumakis, V., Rusu, I.: Weighted parameters in $(P_{5},\\overline{P}_{5})$ -free graphs. Discrete Appl. Math. 80, 255\u2013261 (1997)","journal-title":"Discrete Appl. Math."},{"key":"9197_CR8","first-page":"325","volume":"21","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Ann. Discrete Math. 21, 325\u2013356 (1984)","journal-title":"Ann. Discrete Math."},{"key":"9197_CR9","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01788689","volume":"5","author":"R. Hayward","year":"1989","unstructured":"Hayward, R., Ho\u00e0ng, C.T., Maffray, F.: Optimizing weakly triangulated graphs. Graphs Comb. 5, 339\u2013349 (1989)","journal-title":"Graphs Comb."},{"key":"9197_CR10","unstructured":"Ho\u00e0ng, C.T., Sawada, J., Wang, Z.: Colorability of P 5-free graphs. Manuscript (2005)"},{"key":"9197_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":"9197_CR12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum, New York (1972)"},{"key":"9197_CR13","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/s004930070013","volume":"20","author":"S. Khanna","year":"2000","unstructured":"Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica 20, 393\u2013415 (2000)","journal-title":"Combinatorica"},{"issue":"3","key":"9197_CR14","first-page":"90","volume":"2","author":"D.V. Korobitsyn","year":"1990","unstructured":"Korobitsyn, D.V.: On the complexity of determining the domination number in monogenic classes of graphs. Diskret. Mat. 2(3), 90\u201396 (1990) (in Russian); translation in Discrete Math. Appl. 2(2), 191\u2013199 (1992)","journal-title":"Diskret. Mat."},{"key":"9197_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/3-540-45477-2_23","volume-title":"WG 2001","author":"D. Kral","year":"2001","unstructured":"Kral, D., Kratochvil, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: WG 2001. Lecture Notes in Computer Science, vol. 2204, pp. 254\u2013262. Springer, Berlin (2001)"},{"key":"9197_CR16","unstructured":"Bang Le, V., Randerath, B., Schiermeyer, I.: Two remarks on coloring graphs without long induced paths. Report No. 7\/2006 (Algorithmic Graph Theory), Mathematisches Forschungsinstitut Oberwolfach"},{"key":"9197_CR17","doi-asserted-by":"crossref","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. Discrete Math. 162, 313\u2013317 (1996)","journal-title":"Discrete Math."},{"issue":"1","key":"9197_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00373-003-0540-1","volume":"20","author":"B. Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: Vertex coloring and forbidden subgraphs\u2014a survey. Graphs Comb. 20(1), 1\u201340 (2004)","journal-title":"Graphs Comb."},{"key":"9197_CR19","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0166-218X(03)00446-3","volume":"136","author":"B. Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: 3-colorability \u2208\u2118 for P 6-free graphs. Discrete Appl. Math. 136, 299\u2013313 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9197_CR20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0012-365X(01)00335-1","volume":"251","author":"B. Randerath","year":"2002","unstructured":"Randerath, B., Schiermeyer, I., Tewes, M.: Three-colorability and forbidden subgraphs, II: polynomial algorithms. Discrete Math. 251, 137\u2013153 (2002)","journal-title":"Discrete Math."},{"issue":"1","key":"9197_CR21","first-page":"107","volume":"15","author":"J. Sgall","year":"2001","unstructured":"Sgall, J., Woeginger, G.J.: The complexity of coloring graphs without long induced paths. Acta Cybern. 15(1), 107\u2013117 (2001)","journal-title":"Acta Cybern."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9197-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9197-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9197-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:02Z","timestamp":1559123102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9197-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,29]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["9197"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9197-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5,29]]}}}