{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T16:36:03Z","timestamp":1774974963529,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642106309","type":"print"},{"value":"9783642106316","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10631-6_61","type":"book-chapter","created":{"date-parts":[[2009,12,4]],"date-time":"2009-12-04T07:03:43Z","timestamp":1259910223000},"page":"594-604","source":"Crossref","is-referenced-by-count":21,"title":["A Certifying Algorithm for 3-Colorability of P 5-Free Graphs"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Bruce","sequence":"first","affiliation":[]},{"given":"Ch\u00ednh T.","family":"Ho\u00e0ng","sequence":"additional","affiliation":[]},{"given":"Joe","family":"Sawada","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"61_CR1","doi-asserted-by":"publisher","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\n                5-free graphs. Period. Math. Hungar.\u00a021(4), 303\u2013308 (1990)","journal-title":"Period. Math. Hungar."},{"issue":"3","key":"61_CR2","doi-asserted-by":"publisher","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. Journal of Symbolic Computation\u00a09(3), 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"issue":"1","key":"61_CR3","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Annals of Mathematics\u00a0164(1), 51\u2013229 (2006)","journal-title":"Annals of Mathematics"},{"key":"61_CR4","unstructured":"Ho\u00e0ng, C.T., Kamin\u015bki, M., Lozin, V., Sawada, J., Shu, X.: Deciding k-colorability of P5-free graphs in polynomial time. To appear in Algorithmica"},{"key":"61_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-540-85238-4_31","volume-title":"Mathematical Foundations of Computer Science 2008","author":"C.T. Ho\u00e0ng","year":"2008","unstructured":"Ho\u00e0ng, C.T., Kamin\u015bki, M., Lozin, V., Sawada, J., Shu, X.: A Note on k-Colorability of P5-Free Graphs. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 387\u2013394. Springer, Heidelberg (2008)"},{"issue":"3","key":"61_CR6","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.\u00a02(3), 90\u201396 (1990) (in Russian); Translation in Discrete Mathematics and Applications 2(2), 191-199 (1992)","journal-title":"Diskret. Mat."},{"key":"61_CR7","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. Kral","year":"2001","unstructured":"Kral, D., Kratochvil, 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.\u00a02204, pp. 254\u2013262. Springer, Heidelberg (2001)"},{"issue":"2","key":"61_CR8","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1137\/S0097539703437855","volume":"36","author":"D. Kratsch","year":"2006","unstructured":"Kratsch, D., McConnell, R.M., Mehlhorn, K., Spinrad, J.P.: Certifying algorithms for recognizing interval graphs and permutation graphs. SIAM J. Comput.\u00a036(2), 326\u2013353 (2006)","journal-title":"SIAM J. Comput."},{"key":"61_CR9","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.tcs.2007.09.009","volume":"389","author":"V. Bang Le","year":"2007","unstructured":"Bang Le, V., Randerath, B., Schiermeyer, I.: On the complexity of 4-coloring graphs without long induced paths. Theoretical Computer Science\u00a0389, 330\u2013335 (2007)","journal-title":"Theoretical Computer Science"},{"key":"61_CR10","unstructured":"Mellin, S.: Polynomielle F\u00e4rbungsalgorithmen f\u00fcr P\n                \n                  k\n                -freie Graphen, Diplomarbeit am Institut f\u00fcr Informatik, Universit\u00e4t zu K\u00f6ln (2002)"},{"issue":"1","key":"61_CR11","doi-asserted-by":"publisher","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 \u2013 a survey. Graphs and Combinatorics\u00a020(1), 1\u201340 (2004)","journal-title":"Graphs and Combinatorics"},{"key":"61_CR12","doi-asserted-by":"publisher","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 \n                  \n                    \n                  \n                  $\\in \\mathcal{P}$\n                 for P\n                6-free graphs. Discrete Applied Mathematics\u00a0136, 299\u2013313 (2004)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"61_CR13","first-page":"107","volume":"15","author":"G.J. Woeginger","year":"2001","unstructured":"Woeginger, G.J., Sgall, J.: The complexity of coloring graphs without long induced paths. Acta Cybernetica\u00a015(1), 107\u2013117 (2001)","journal-title":"Acta Cybernetica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10631-6_61","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:58:36Z","timestamp":1558285116000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10631-6_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106309","9783642106316"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}