{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:07Z","timestamp":1759063687810,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480533"},{"type":"electronic","value":"9783662480540"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_12","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"139-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Bounding the Clique-Width of H-free Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[]},{"given":"Konrad K.","family":"Dabrowski","sequence":"additional","affiliation":[]},{"given":"Shenwei","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"issue":"1\u20132","key":"12_CR1","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybernetica"},{"key":"12_CR2","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)"},{"issue":"1\u20132","key":"12_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(03)00266-X","volume":"138","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A.: ($$P_5$$, diamond)-free graphs revisited: structure and linear time optimization. Discrete Appl. Math. 138(1\u20132), 13\u201327 (2004)","journal-title":"Discrete Appl. Math."},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding the clique-width of $$H$$-free split graphs. In: Proceedings of EuroComb ENDM (to appear, 2015)","DOI":"10.1016\/j.endm.2015.06.069"},{"issue":"4","key":"12_CR5","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. Theor. Comput. Sys. 39(4), 561\u2013590 (2006)","journal-title":"Theor. Comput. Sys."},{"issue":"1","key":"12_CR6","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 Math. Theor. Comput. Sci. 8(1), 173\u2013188 (2006)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"2","key":"12_CR7","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 Appl. Math. 145(2), 155\u2013166 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"12_CR8","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. Int. J. Found. Comput. Sci. 15(1), 163\u2013185 (2004)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"12_CR9","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 Appl. Math. 145(2), 232\u2013241 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"12_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.ipl.2003.11.002","volume":"89","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Le, V.B., de Ridder, H.N.: Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes. Inf. Process. Lett. 89(4), 165\u2013173 (2004)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"12_CR11","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. Inf. Process. Lett. 84(5), 251\u2013259 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"12_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0166-218X(03)00389-5","volume":"132","author":"A Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Mosca, R.: On the structure and stability number of $$P_5$$- and co-chair-free graphs. Discrete Appl. Math. 132(1\u20133), 47\u201365 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"12_CR13","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1016\/j.dam.2011.03.020","volume":"160","author":"DG Corneil","year":"2012","unstructured":"Corneil, D.G., Habib, M., Lanlignel, J.-M., Reed, B.A., Rotics, U.: Polynomial-time recognition of clique-width $$\\le 3$$ graphs. Discrete Appl. Math. 160(6), 834\u2013865 (2012)","journal-title":"Discrete Appl. Math."},{"key":"12_CR14","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 J. Comput. 34, 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"12_CR15","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. Theor. Comput. Sys. 33(2), 125\u2013150 (2000)","journal-title":"Theor. Comput. Sys."},{"issue":"1\u20133","key":"12_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"12_CR17","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. Theoret. Comput. Sci. 522, 34\u201343 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1007\/978-3-319-15579-1_53","volume-title":"Language and Automata Theory and Applications","author":"KK Dabrowski","year":"2015","unstructured":"Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding clique-width via perfect graphs. In: Dediu, A.-H., Formenti, E., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2015. LNCS, vol. 8977, pp. 676\u2013688. Springer, Heidelberg (2015)"},{"issue":"7","key":"12_CR19","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 Math. 312(7), 1372\u20131385 (2012)","journal-title":"Discrete Math."},{"key":"12_CR20","unstructured":"Dabrowski, K.K., Paulusma, D.: Classifying the clique-width of $${H}$$-free bipartite graphs. Discrete Appl. Math. (to appear)"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-319-18173-8_12","volume-title":"Algorithms and Complexity","author":"KK Dabrowski","year":"2015","unstructured":"Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 167\u2013181. Springer, Heidelberg (2015)"},{"key":"12_CR22","unstructured":"de Ridder, H.N., et al.: Information System on Graph Classes and their Inclusions (2001\u20132013). www.graphclasses.org"},{"issue":"1","key":"12_CR23","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01195324","volume":"9","author":"C De Simone","year":"1993","unstructured":"De Simone, C.: On the vertex packing problem. Graphs Comb. 9(1), 19\u201330 (1993)","journal-title":"Graphs Comb."},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/3-540-45477-2_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"W Espelage","year":"2001","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117\u2013128. Springer, Heidelberg (2001)"},{"issue":"2","key":"12_CR25","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 J. Discrete Math. 23(2), 909\u2013939 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR26","first-page":"311","volume":"XIX","author":"S F\u00f6ldes","year":"1977","unstructured":"F\u00f6ldes, S., Hammer, P.L.: Split graphs. Congressus Numerantium XIX, 311\u2013315 (1977)","journal-title":"Congressus Numerantium"},{"key":"12_CR27","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2014","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland Publishing Company, Amsterdam (2014)"},{"issue":"03","key":"12_CR28","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. Int. J. Found. Comput. Sci. 11(03), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"12_CR29","unstructured":"Gurski, F.: Graph operations on clique-width bounded graphs. CoRR, abs\/cs\/0701185 (2007)"},{"issue":"12","key":"12_CR30","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 Appl. Math. 157(12), 2747\u20132761 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"2\u20133","key":"12_CR31","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 Appl. Math. 126(2\u20133), 197\u2013221 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"12_CR32","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s00373-013-1290-3","volume":"30","author":"N Korpelainen","year":"2014","unstructured":"Korpelainen, N., Lozin, V.V., Mayhill, C.: Split permutation graphs. Graphs Comb. 30(3), 633\u2013646 (2014)","journal-title":"Graphs Comb."},{"key":"12_CR33","unstructured":"Le, H.-O.: Contributions to clique-width of graphs. Ph.D. thesis, University of Rostock (2003). Cuvillier Verlag G\u00f6ttingen (2004)"},{"issue":"1","key":"12_CR34","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 J. Discrete Math. 18(1), 195\u2013206 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"03","key":"12_CR35","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. Int. J. Found. Comput. Sci. 10(03), 329\u2013348 (1999)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"12_CR36","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1002\/jgt.3190150108","volume":"15","author":"S Olariu","year":"1991","unstructured":"Olariu, S.: On the homogeneous representation of interval graphs. J. Graph Theor. 15(1), 65\u201380 (1991)","journal-title":"J. Graph Theor."},{"issue":"1","key":"12_CR37","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/1435375.1435385","volume":"5","author":"S-I Oum","year":"2008","unstructured":"Oum, S.-I.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms 5(1), 10 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"1\u20133","key":"12_CR38","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. Theoret. Comput. Sci. 377(1\u20133), 260\u2013267 (2007)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T14:19:26Z","timestamp":1675865966000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_12","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":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}