{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:28Z","timestamp":1759638988574},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319455860"},{"type":"electronic","value":"9783319455877"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-45587-7_4","type":"book-chapter","created":{"date-parts":[[2016,9,9]],"date-time":"2016-09-09T00:01:21Z","timestamp":1473379281000},"page":"38-49","source":"Crossref","is-referenced-by-count":5,"title":["Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions"],"prefix":"10.1007","author":[{"given":"Dani\u00ebl","family":"Paulusma","sequence":"first","affiliation":[]},{"given":"Christophe","family":"Picouleau","sequence":"additional","affiliation":[]},{"given":"Bernard","family":"Ries","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,10]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/s00373-013-1380-2","volume":"31","author":"C Bazgan","year":"2015","unstructured":"Bazgan, C., Bentz, C., Picouleau, C., Ries, B.: Blockers for the stability number and the chromatic number. Graphs Comb. 31, 73\u201390 (2015)","journal-title":"Graphs Comb."},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/978-3-642-19222-7_17","volume-title":"Combinatorial Algorithms","author":"C Bazgan","year":"2011","unstructured":"Bazgan, C., Toubaline, S., Tuza, Z.: Complexity of most vital nodes for independent set in graphs related to tree structures. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 154\u2013166. Springer, Heidelberg (2011)"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"1933","DOI":"10.1016\/j.dam.2011.06.023","volume":"159","author":"C Bazgan","year":"2011","unstructured":"Bazgan, C., Toubaline, S., Tuza, Z.: The most vital nodes with respect to independent set and vertex cover. Discrete Appl. Math. 159, 1933\u20131946 (2011)","journal-title":"Discrete Appl. Math."},{"key":"4_CR4","unstructured":"Bentz, C., Costa, M.-C., de Werra, D., Picouleau, C., Ries, B.: Weighted Transversals and blockers for some optimization problems in graphs. In: Progress in Combinatorial Optimization. ISTE-WILEY (2012)"},{"key":"4_CR5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1007\/s10878-010-9334-6","volume":"22","author":"M-C Costa","year":"2011","unstructured":"Costa, M.-C., de Werra, D., Picouleau, C.: Minimum $$d$$ -blockers and $$d$$ -transversals in graphs. J. Comb. Optim. 22, 857\u2013872 (2011)","journal-title":"J. Comb. Optim."},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1007\/978-3-319-18173-8_14","volume-title":"Algorithms and Complexity","author":"\u00d6Y Diner","year":"2015","unstructured":"Diner, \u00d6.Y., Paulusma, D., Picouleau, C., Ries, B.: Contraction blockers for graphs with forbidden induced paths. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 194\u2013207. Springer, Heidelberg (2015)"},{"key":"4_CR8","first-page":"311","volume":"19","author":"S F\u00f6ldes","year":"1977","unstructured":"F\u00f6ldes, S., Hammer, P.L.: Split graphs. Congressus Numerantium 19, 311\u2013315 (1977). 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing","journal-title":"Congressus Numerantium"},{"key":"4_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"4_CR11","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."},{"key":"4_CR12","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(88)90143-3","volume":"28","author":"S Olariu","year":"1988","unstructured":"Olariu, S.: Paw-free graphs. Inf. Process. Lett. 28, 53\u201354 (1988)","journal-title":"Inf. Process. Lett."},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1002\/net.21556","volume":"64","author":"FM Pajouh","year":"2014","unstructured":"Pajouh, F.M., Boginski, V., Pasiliao, E.L.: Minimum vertex blocker clique problem. Networks 64, 48\u201364 (2014)","journal-title":"Networks"},{"key":"4_CR14","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on the stable sets and coloring of graphs. Comment. Math. Univ. Carolin. 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.disc.2009.08.009","volume":"310","author":"B Ries","year":"2010","unstructured":"Ries, B., Bentz, C., Picouleau, C., de Werra, D., Costa, M.-C., Zenklusen, R.: Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid. Discrete Math. 310, 132\u2013146 (2010)","journal-title":"Discrete Math."},{"key":"4_CR16","unstructured":"Toubaline, S.: D\u00e9termination des \u00e9l\u00e9ments les plus vitaux pour des probl\u00e8mes de graphes. Ph.D. Thesis, Universit\u00e9 Paris-Dauphine (2010)"},{"key":"4_CR17","volume-title":"Introduction to Graph Theory","author":"DB West","year":"1996","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice-Hall, Upper Saddle River (1996)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45587-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T18:18:18Z","timestamp":1498328298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-45587-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319455860","9783319455877"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45587-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}