{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T23:30:35Z","timestamp":1725579035669},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642192210"},{"type":"electronic","value":"9783642192227"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_30","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T08:03:12Z","timestamp":1300089792000},"page":"291-302","source":"Crossref","is-referenced-by-count":0,"title":["Graphs of Separability at Most Two: Structural Characterizations and Their Consequences"],"prefix":"10.1007","author":[{"given":"Ferdinando","family":"Cicalese","sequence":"first","affiliation":[]},{"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl.\u00a0Math.\u00a023, 11\u201324 (1989)","journal-title":"Discrete Appl.\u00a0Math."},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/net.3230190206","volume":"19","author":"E. Balas","year":"1989","unstructured":"Balas, E., Yu, C.S.: On graphs with polynomially solvable maximum-weight clique problem. Networks\u00a019, 247\u2013253 (1989)","journal-title":"Networks"},{"key":"30_CR3","first-page":"114","volume":"10","author":"C. Berge","year":"1961","unstructured":"Berge, C.: F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw.\u00a0deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe\u00a010, 114 (1961)","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"30_CR4","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.: On the clique-width of graphs in hereditary classes. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 44\u201354. Springer, Heidelberg (2002)"},{"key":"30_CR5","series-title":"North-Holland Math. Stud.","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0304-0208(08)72939-6","volume-title":"Topics on Perfect Graphs","author":"M. Burlet","year":"1984","unstructured":"Burlet, M., Fonlupt, J.: Polynomial algorithm to recognize a Meyniel graph. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on Perfect Graphs. North-Holland Math. Stud., vol.\u00a088, pp. 253\u2013278. North-Holland, Amsterdam (1984)"},{"key":"30_CR6","unstructured":"Chudnovsky, M.: The structure of bull-free graphs I\u2013III (submitted)"},{"issue":"2","key":"30_CR7","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. Ann. of Math.\u00a0164(2), 51\u2013229 (2006)","journal-title":"Ann. of Math."},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1016\/j.jctb.2007.06.007","volume":"98","author":"M. Chudnovsky","year":"2008","unstructured":"Chudnovsky, M., Seymour, P.: Claw-free graphs. IV. Decomposition theorem. JCTB\u00a098, 839\u2013938 (2008)","journal-title":"JCTB"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0095-8956(02)00021-7","volume":"87","author":"M. Conforti","year":"2003","unstructured":"Conforti, M., Cornu\u00e9jols, G.: Graphs without odd holes, parachutes or proper wheels: a generalization of Meyniel graphs and of line graphs of bipartite graphs. JCTB\u00a087, 300\u2013330 (2003)","journal-title":"JCTB"},{"key":"30_CR10","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/(SICI)1097-0118(199904)30:4<289::AID-JGT4>3.0.CO;2-3","volume":"30","author":"M. Conforti","year":"1993","unstructured":"Conforti, M., Cornu\u00e9jols, G., Kapoor, A., Vu\u0161kovi\u0107, K.: Even and odd holes in cap-free graphs. J.\u00a0Graph Theory\u00a030, 289\u2013308 (1993)","journal-title":"J.\u00a0Graph Theory"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/3-540-59408-6_61","volume-title":"Integer Programming and Combinatorial Optimization","author":"M. Conforti","year":"1995","unstructured":"Conforti, M., Cornu\u00e9jols, G., Kapoor, A., Vu\u0161kovi\u0107, K.: A Mickey-mouse decomposition theorem. In: Balas, E., Clausen, J. (eds.) IPCO 1995. LNCS, vol.\u00a0920, pp. 321\u2013328. Springer, Heidelberg (1995)"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1002\/jgt.10006","volume":"39","author":"M. Conforti","year":"2002","unstructured":"Conforti, M., Cornu\u00e9jols, G., Kapoor, A., Vu\u0161kovi\u0107, K.: Even-hole-free graphs. I. Decomposition theorem. J. Graph Theory\u00a039, 6\u201349 (2002)","journal-title":"J. Graph Theory"},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF01196132","volume":"17","author":"M. Conforti","year":"1997","unstructured":"Conforti, M., Cornu\u00e9jols, G., Kapoor, A., Vu\u0161kovi\u0107, K.: Universally signable graphs. Combinatorica\u00a017, 67\u201377 (1997)","journal-title":"Combinatorica"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s004930070028","volume":"20","author":"M. Conforti","year":"2000","unstructured":"Conforti, M., Gerards, B., Kapoor, A.: A theorem of Truemper. Combinatorica\u00a020, 15\u201326 (2000)","journal-title":"Combinatorica"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"D.G. Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J.\u00a0Comput.\u00a034, 825\u2013847 (2005)","journal-title":"SIAM J.\u00a0Comput."},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1142\/9789812384720_0005","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformation","author":"B. Courcelle","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of Graph Grammars and Computing by Graph Transformation, vol.\u00a01, pp. 313\u2013400. World Sci.\u00a0Publishing, River Edge (1997)"},{"key":"30_CR17","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 Comput. Syst.\u00a033, 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"30_CR18","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"30_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"30_CR20","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.\u00a02204, pp. 117\u2013128. Springer, Heidelberg (2001)"},{"key":"30_CR21","first-page":"719","volume":"299","author":"M.U. Gerber","year":"2003","unstructured":"Gerber, M.U., Kobler, D.: Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theoret.\u00a0Comput.\u00a0Sci.\u00a0299, 719\u2013734 (2003)","journal-title":"Theoret.\u00a0Comput.\u00a0Sci."},{"key":"30_CR22","first-page":"801","volume":"10","author":"A. Gy\u00e1rf\u00e1s","year":"1973","unstructured":"Gy\u00e1rf\u00e1s, A.: On Ramsey covering problems. Coll. Math. Soc. J\u00e1nos Bolyai\u00a010, 801\u2013816 (1973)","journal-title":"Coll. Math. Soc. J\u00e1nos Bolyai"},{"key":"30_CR23","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1016\/j.jctb.2008.12.005","volume":"99","author":"T. Kloks","year":"2009","unstructured":"Kloks, T., M\u00fcller, H., Vu\u0161kovi\u0107, K.: Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences. JCTB\u00a099, 733\u2013800 (2009)","journal-title":"JCTB"},{"key":"30_CR24","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 Math.\u00a0126, 197\u2013221 (2003)","journal-title":"Discrete Applied Math."},{"key":"30_CR25","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1142\/S0129054199000241","volume":"10","author":"J.A. Makowsky","year":"1999","unstructured":"Makowsky, J.A., Rotics, U.: On the clique-width of graphs with few P\n                4\u2019s. International J.\u00a0Foundations of Computer Science\u00a010, 329\u2013348 (1999)","journal-title":"International J.\u00a0Foundations of Computer Science"},{"key":"30_CR26","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0019-9958(83)80048-5","volume":"56","author":"G.L. Miller","year":"1983","unstructured":"Miller, G.L.: Isomorphism of graphs which are pairwise k-separable. Information and Control\u00a056, 21\u201333 (1983)","journal-title":"Information and Control"},{"key":"30_CR27","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica\u00a07, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"30_CR28","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math.\u00a055, 221\u2013232 (1985)","journal-title":"Discrete Math."},{"key":"30_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/jgt.20405","volume":"63","author":"N. Trotignon","year":"2009","unstructured":"Trotignon, N., Vu\u0161kovi\u0107, K.: A structure theorem for graphs with no cycle with a unique chord and its consequences. J. Graph Theory\u00a063, 31\u201367 (2009)","journal-title":"J. Graph Theory"},{"key":"30_CR30","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S. Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput.\u00a06, 505\u2013517 (1977)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T10:52:19Z","timestamp":1558435939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}