{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T22:40:00Z","timestamp":1743115200988,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319123394"},{"type":"electronic","value":"9783319123400"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12340-0_11","type":"book-chapter","created":{"date-parts":[[2014,10,20]],"date-time":"2014-10-20T04:27:23Z","timestamp":1413779243000},"page":"129-138","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A New Characterization of $$P_k$$-free Graphs"],"prefix":"10.1007","author":[{"given":"Eglantine","family":"Camby","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF02352694","volume":"21","author":"G B\u00e1cso","year":"1990","unstructured":"B\u00e1cso, G., Tuza, Z.: Dominating cliques in $${P}_5$$-free graphs. Period. Math. Hungar. 21, 303\u2013308 (1990)","journal-title":"Period. Math. Hungar."},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1016\/j.ejc.2011.12.008","volume":"34","author":"H Broersma","year":"2013","unstructured":"Broersma, H., Fomin, F.V., Golovach, P.A., Paulusma, D.: Three complexity results on coloring $${P}_k$$-free graphs. Europ. J. Combin. 34, 609\u2013619 (2013)","journal-title":"Europ. J. Combin."},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2014.05.029","volume":"177","author":"E Camby","year":"2014","unstructured":"Camby, E., Schaudt, O.: The price of connectivity for dominating sets: upper bounds and complexity. Disc. Appl. Math. 177, 53\u201359 (2014)","journal-title":"Disc. Appl. Math."},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0012-365X(90)90353-J","volume":"86","author":"MB Cozzens","year":"1990","unstructured":"Cozzens, M.B., Kelleher, L.L.: Dominating cliques in graphs. Disc. Math. 86, 101\u2013116 (1990)","journal-title":"Disc. Math."},{"key":"11_CR5","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Co., New York (1979)"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"CT Ho\u00e1ng","year":"2010","unstructured":"Ho\u00e1ng, C.T., Kaminski, M., Lozin, V.V., Sawada, J., Shu, X.: Deciding $$k$$-colorability of $${P}_5$$-free graphs in polynomial time. Algorithmica 57, 74\u201381 (2010)","journal-title":"Algorithmica"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-642-40313-2_49","volume-title":"Mathematical Foundations of Computer Science 2013","author":"S Huang","year":"2013","unstructured":"Huang, S.: Improved complexity results on k-coloring P\n                $$_{\\mathit{t}}$$-free graphs. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 551\u2013558. Springer, Heidelberg (2013)"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1016\/j.dam.2006.11.005","volume":"155","author":"J Liu","year":"2007","unstructured":"Liu, J., Peng, Y., Zhao, C.: Characterization of $${P}_6$$-free graphs. Disc. App. Math. 155, 1038\u20131043 (2007)","journal-title":"Disc. App. Math."},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0012-365X(93)E0111-G","volume":"135","author":"J Liu","year":"1994","unstructured":"Liu, J., Zhou, H.: Dominating subgraphs in graphs with some forbidden structures. Disc. Math. 135, 163\u2013168 (1994)","journal-title":"Disc. Math."},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in $${P}_5$$-free graphs in polynomial time. In: Proceedings of SODA, pp. 570\u2013581. SIAM (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"11_CR11","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 $$\\in \\cal P$$ for $${P}_6$$-free graphs. Disc. App. Math. 136, 299\u2013313 (2004)","journal-title":"Disc. App. Math."},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"van \u2019t Hof, P., Paulusma, D.: A new characterization of $${P}_6$$-free graphs. In: Proceedings of COCOON, pp. 415\u2013424 (2008)","DOI":"10.1007\/978-3-540-69733-6_41"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.dam.2008.08.025","volume":"158","author":"P van \u2019t Hof","year":"2010","unstructured":"van \u2019t Hof, P., Paulusma, D.: A new characterization of $${P}_6$$-free graphs. Disc. App. Math. 158, 731\u2013740 (2010)","journal-title":"Disc. App. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12340-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T14:49:26Z","timestamp":1676904566000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12340-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319123394","9783319123400"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12340-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"21 October 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}