{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:22:21Z","timestamp":1742948541243,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_53","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"676-688","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Bounding Clique-Width via Perfect Graphs"],"prefix":"10.1007","author":[{"given":"Konrad Kazimierz","family":"Dabrowski","sequence":"first","affiliation":[]},{"given":"Shenwei","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"53_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-36136-7_5","volume-title":"Algorithms and Computation","author":"R Boliac","year":"2002","unstructured":"Boliac, R., Lozin, V.V.: On the clique-width of graphs in hereditary classes. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 44\u201354. Springer, Heidelberg (2002)"},{"key":"53_CR2","unstructured":"Bonomo, F., Grippo, L.N., Milani\u010d, M., Safe, M.D.: Graphs of power-bounded clique-width. arXiv abs\/1402.2135 (2014)"},{"issue":"4","key":"53_CR3","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s00224-005-1199-1","volume":"39","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Engelfriet, J., Le, H.O., Lozin, V.V.: Clique-width for 4-vertex forbidden subgraphs. Theory of Computing Systems 39(4), 561\u2013590 (2006)","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"53_CR4","first-page":"173","volume":"8","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Klembt, T., Mahfud, S.: $$P_6$$- and triangle-free graphs revisited: structure and bounded clique-width. Discrete Mathematics and Theoretical Computer Science 8(1), 173\u2013188 (2006)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"issue":"2","key":"53_CR5","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.dam.2004.01.009","volume":"145","author":"A Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the structure of ($$P_5$$, gem)-free graphs. Discrete Applied Mathematics 145(2), 155\u2013166 (2005)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"53_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S0129054104002364","volume":"15","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Le, H.O., Mosca, R.: Gem- and co-gem-free graphs have bounded clique-width. International Journal of Foundations of Computer Science 15(1), 163\u2013185 (2004)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"2","key":"53_CR7","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.dam.2004.01.014","volume":"145","author":"A Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Le, H.O., Mosca, R.: Chordal co-gem-free and ($$P_5$$, gem)-free graphs have bounded clique-width. Discrete Applied Mathematics 145(2), 232\u2013241 (2005)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"53_CR8","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(02)00291-0","volume":"84","author":"A Brandst\u00e4dt","year":"2002","unstructured":"Brandst\u00e4dt, A., Mahfud, S.: Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. Information Processing Letters 84(5), 251\u2013259 (2002)","journal-title":"Information Processing Letters"},{"issue":"2\u20133","key":"53_CR9","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0166-218X(03)00180-X","volume":"129","author":"A Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Mosca, R.: On variations of $$P_4$$-sparse graphs. Discrete Applied Mathematics 129(2\u20133), 521\u2013532 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"53_CR10","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 164, 51\u2013229 (2006)","journal-title":"Annals of Mathematics"},{"key":"53_CR11","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM Journal on Computing 34, 825\u2013847 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"1\u20132","key":"53_CR12","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.ipl.2013.09.012","volume":"114","author":"B Courcelle","year":"2014","unstructured":"Courcelle, B.: Clique-width and edge contraction. Information Processing Letters 114(1\u20132), 42\u201344 (2014)","journal-title":"Information Processing Letters"},{"issue":"2","key":"53_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems 33(2), 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2013.12.004","volume":"522","author":"KK Dabrowski","year":"2014","unstructured":"Dabrowski, K.K., Golovach, P.A., Paulusma, D.: Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science 522, 34\u201343 (2014)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"53_CR15","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1016\/j.disc.2011.12.012","volume":"312","author":"KK Dabrowski","year":"2012","unstructured":"Dabrowski, K.K., Lozin, V.V., Raman, R., Ries, B.: Colouring vertices of triangle-free graphs without forests. Discrete Mathematics 312(7), 1372\u20131385 (2012)","journal-title":"Discrete Mathematics"},{"key":"53_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-319-08783-2_42","volume-title":"Computing and Combinatorics","author":"KK Dabrowski","year":"2014","unstructured":"Dabrowski, K.K., Paulusma, D.: Classifying the clique-width of H-free bipartite graphs. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds.) COCOON 2014. LNCS, vol. 8591, pp. 489\u2013500. Springer, Heidelberg (2014)"},{"key":"53_CR17","doi-asserted-by":"crossref","unstructured":"Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. CoRR abs\/1405.7092 (2014)","DOI":"10.1007\/978-3-319-18173-8_12"},{"issue":"2","key":"53_CR18","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-Complete. SIAM Journal on Discrete Mathematics 23(2), 909\u2013939 (2009)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"03","key":"53_CR19","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science 11(03), 423\u2013443 (2000)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"53_CR20","unstructured":"Gurski, F.: Graph operations on clique-width bounded graphs. CoRR abs\/cs\/0701185 (2007)"},{"key":"53_CR21","first-page":"39","volume":"132","author":"\u00d6 Johansson","year":"1998","unstructured":"Johansson, \u00d6.: Clique-decomposition, NLC-decomposition, and modular decomposition - relationships and results for random graphs. Congressus Numerantium 132, 39\u201360 (1998)","journal-title":"Congressus Numerantium"},{"issue":"12","key":"53_CR22","doi-asserted-by":"publisher","first-page":"2747","DOI":"10.1016\/j.dam.2008.08.022","volume":"157","author":"M Kami\u0144ski","year":"2009","unstructured":"Kami\u0144ski, M., Lozin, V.V., Milani\u010d, M.: Recent developments on graphs of bounded clique-width. Discrete Applied Mathematics 157(12), 2747\u20132761 (2009)","journal-title":"Discrete Applied Mathematics"},{"issue":"2\u20133","key":"53_CR23","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics 126(2\u20133), 197\u2013221 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"53_CR24","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/S0895480102419755","volume":"18","author":"VV Lozin","year":"2004","unstructured":"Lozin, V.V., Rautenbach, D.: On the band-, tree-, and clique-width of graphs with bounded vertex degree. SIAM Journal on Discrete Mathematics 18(1), 195\u2013206 (2004)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"53_CR25","first-page":"57","volume":"34","author":"VV Lozin","year":"2006","unstructured":"Lozin, V.V., Rautenbach, D.: The tree- and clique-width of bipartite graphs in special classes. Australasian Journal of Combinatorics 34, 57\u201367 (2006)","journal-title":"Australasian Journal of Combinatorics"},{"issue":"02","key":"53_CR26","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1142\/S0129054108005772","volume":"19","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Volz, J.: The clique-width of bipartite graphs in monogenic classes. International Journal of Foundations of Computer Science 19(02), 477\u2013494 (2008)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"03","key":"53_CR27","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1142\/S0129054199000241","volume":"10","author":"JA Makowsky","year":"1999","unstructured":"Makowsky, J.A., Rotics, U.: On the clique-width of graphs with few $$P_4$$\u2019s. International Journal of Foundations of Computer Science 10(03), 329\u2013348 (1999)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1","key":"53_CR28","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/1435375.1435385","volume":"5","author":"SI Oum","year":"2008","unstructured":"Oum, S.I.: Approximating rank-width and clique-width quickly. ACM Transactions on Algorithms 5(1), 10 (2008)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"53_CR29","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"SI Oum","year":"2006","unstructured":"Oum, S.I., Seymour, P.D.: Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B 96(4), 514\u2013528 (2006)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1\u20133","key":"53_CR30","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.tcs.2007.03.043","volume":"377","author":"M Rao","year":"2007","unstructured":"Rao, M.: MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoretical Computer Science 377(1\u20133), 260\u2013267 (2007)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T02:26:17Z","timestamp":1675131977000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}