{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:10:57Z","timestamp":1725541857070},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_30","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"341-352","source":"Crossref","is-referenced-by-count":0,"title":["Finding Induced Paths of Given Parity in Claw-Free Graphs"],"prefix":"10.1007","author":[{"given":"Pim","family":"van \u2019t Hof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Kami\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"30_CR1","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1145\/103516.103517","volume":"38","author":"E.M. Arkin","year":"1991","unstructured":"Arkin, E.M., Papadimitriou, C.H., Yannakakis, M.: Modularity of cycles and paths in graphs. Journal of the ACM\u00a038(2), 255\u2013274 (1991)","journal-title":"Journal of the ACM"},{"issue":"1-3","key":"30_CR2","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0166-218X(93)90230-L","volume":"44","author":"S.R. Arikati","year":"1993","unstructured":"Arikati, S.R., Peled, U.N.: A linear algorithm for the group path problem on chordal graphs. Discrete Applied Mathematics\u00a044(1-3), 185\u2013190 (1993)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"30_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0166-218X(95)00086-7","volume":"65","author":"S.R. Arikati","year":"1996","unstructured":"Arikati, S.R., Peled, U.N.: A polynomial algorithm for the parity path problem on perfectly orientable graphs. Discrete Applied Mathematics\u00a065(1), 5\u201320 (1996)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"30_CR4","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/BF01931279","volume":"31","author":"S.R. Arikati","year":"1991","unstructured":"Arikati, S.R., Rangan, C.P., Manacher, G.K.: Efficient reduction for path problems on circular-arc graphs. BIT\u00a031(2), 182\u2013193 (1991)","journal-title":"BIT"},{"key":"30_CR5","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. Wissenschaftliche Zeitschrift der Martin-Luther-Universit\u00e4t Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe\u00a010, 114 (1961) (in German)","journal-title":"Wissenschaftliche Zeitschrift der Martin-Luther-Universit\u00e4t Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe"},{"issue":"1","key":"30_CR6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0012-365X(91)90098-M","volume":"90","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D.: On the complexity of testing for odd holes and induced odd paths. Discrete Mathematics\u00a090(1), 85\u201392 (1991)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"30_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M. Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P.D., Vu\u0161kovi\u0107, K.: Recognizing Berge Graphs. Combinatorica\u00a025(2), 143\u2013186 (2005)","journal-title":"Combinatorica"},{"key":"30_CR8","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.D., Thomas, R.: The strong perfect graph theorem. Annals of Mathematics\u00a0164, 51\u2013229 (2006)","journal-title":"Annals of Mathematics"},{"key":"30_CR9","unstructured":"Chudnovsky, M., Seymour, P.D.: The three-in-a-tree problem. Combinatorica (to appear), manuscript, \n                  \n                    http:\/\/www.columbia.edu\/~mc2775\/threeinatree.pdf"},{"key":"30_CR10","unstructured":"Chudnovsky, M., Seymour, P.D.: Three-colourable perfect graphs without even pairs (submitted for publication), manuscript, \n                  \n                    http:\/\/www.columbia.edu\/~mc2775\/K4evenpairs.ps"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0095-8956(88)90085-8","volume":"44","author":"V. Chv\u00e1tal","year":"1988","unstructured":"Chv\u00e1tal, V., Sbihi, N.: Recognizing claw-free perfect graphs. Journal of Combinatorial Theory, Series B\u00a044, 154\u2013176 (1988)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jctb.1993.1049","volume":"59","author":"D.G. Corneil","year":"1993","unstructured":"Corneil, D.G., Fonlupt, J.: Stable set bonding in perfect graphs and parity graphs. Journal of Combinatorial Theory, Series B\u00a059, 1\u201314 (1993)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"17","key":"30_CR13","doi-asserted-by":"publisher","first-page":"3552","DOI":"10.1016\/j.dam.2009.02.009","volume":"157","author":"N. Derhy","year":"2009","unstructured":"Derhy, N., Picouleau, C.: Finding induced trees. Discrete Applied Mathematics\u00a0157(17), 3552\u20133557 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0012-365X(96)00174-4","volume":"165-166","author":"H. Everett","year":"1997","unstructured":"Everett, H., de Figueiredo, C.M.H., Sales, C.L., Maffray, F., Porto, O., Reed, B.A.: Path parity and perfection. Discrete Mathematics\u00a0165-166, 233\u2013252 (1997)","journal-title":"Discrete Mathematics"},{"key":"30_CR15","first-page":"67","volume-title":"Perfect Graphs","author":"H. Everett","year":"2001","unstructured":"Everett, H., de Figueiredo, C.M.H., Linhares Sales, C., Maffray, F., Porto, O., Reed, B.A.: In: Ramirez-Alfonsin, L., Reed, B.A. (eds.) Perfect Graphs, pp. 67\u201392. Wiley, Chichester (2001)"},{"issue":"1-3","key":"30_CR16","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0166-218X(98)00139-5","volume":"91","author":"C.M.H. Figueiredo de","year":"1999","unstructured":"de Figueiredo, C.M.H., Gimbel, J.G., Mello, C.P., Szwarcfiter, J.L.: Even and odd pairs in comparability and in P\n                4-comparability graphs. Discrete Applied Mathematics\u00a091(1-3), 293\u2013297 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR17","first-page":"83","volume":"16","author":"J. Fonlupt","year":"1982","unstructured":"Fonlupt, J., Uhry, J.P.: Transformations which preserve perfectness and H-perfectness of graphs. Annals of Discrete Mathematics\u00a016, 83\u201385 (1982)","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"30_CR18","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0895480197329089","volume":"13","author":"C.T. Ho\u00e0ng","year":"2000","unstructured":"Ho\u00e0ng, C.T., Le, V.B.: Recognizing perfect 2-split graphs. SIAM Journal on Discrete Mathematics\u00a013(1), 48\u201355 (2000)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"30_CR19","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1145\/23005.31330","volume":"34","author":"W.-L. Hsu","year":"1987","unstructured":"Hsu, W.-L.: Recognizing planar perfect graphs. Journal of the ACM\u00a034(2), 255\u2013288 (1987)","journal-title":"Journal of the ACM"},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1002\/net.3230140403","volume":"14","author":"A.S. LaPaugh","year":"1984","unstructured":"LaPaugh, A.S., Papadimitriou, C.H.: The even-path problem for graphs and digraphs. Networks\u00a014, 507\u2013513 (1984)","journal-title":"Networks"},{"issue":"17","key":"30_CR21","doi-asserted-by":"publisher","first-page":"3540","DOI":"10.1016\/j.dam.2009.02.015","volume":"157","author":"B. L\u00e9v\u00eaque","year":"2009","unstructured":"L\u00e9v\u00eaque, B., Lin, D.Y., Maffray, F., Trotignon, N.: Detecting induced subgraphs. Discrete Applied Mathematics\u00a0157(17), 3540\u20133551 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR22","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1006\/jctb.1998.1841","volume":"74","author":"C. Linhares Sales","year":"1998","unstructured":"Linhares Sales, C., Maffray, F.: Even pairs in claw-free perfect graphs. Journal of Combinatorial Theory, Series B\u00a074, 169\u2013191 (1998)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"30_CR23","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0195-6698(87)80037-9","volume":"8","author":"H. Meyniel","year":"1987","unstructured":"Meyniel, H.: A new property of critical imperfect graphs and some consequences. European Journal of Combinatorics\u00a08, 313\u2013316 (1987)","journal-title":"European Journal of Combinatorics"},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"N.D. Roussopoulos","year":"1973","unstructured":"Roussopoulos, N.D.: A max {m,n} algorithm for determining the graph H from its line graph G. Information Processing Letters\u00a02, 108\u2013112 (1973)","journal-title":"Information Processing Letters"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"Sampaio, R.M., Sales, C.L.: On the complexity of finding even pairs in planar perfect graphs. In: Brazilian Symposium on Graphs, Algorithms and Combinatorics 2001, Fortaleza. Electronic Notes in Discrete Mathematics, vol.\u00a07, pp. 186\u2013189 (2001)","DOI":"10.1016\/S1571-0653(04)00256-2"},{"issue":"3","key":"30_CR26","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0166-218X(95)00065-Y","volume":"68","author":"C.R. Satyan","year":"1996","unstructured":"Satyan, C.R., Pandu Rangan, C.: The parity path problem on some subclasses of perfect graphs. Discrete Applied Mathematics\u00a068(3), 293\u2013302 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR27","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 Mathematics\u00a055, 221\u2013232 (1985)","journal-title":"Discrete Mathematics"},{"key":"30_CR28","unstructured":"Trotignon, N.: Graphes parfaits: Structure et algorithmes. PhD Thesis, Universit\u00e9 Joseph Fourier - Grenoble I (2004) (in French)"},{"key":"30_CR29","first-page":"281","volume":"21","author":"S.H. Whitesides","year":"1984","unstructured":"Whitesides, S.H.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. Annals of Discrete Mathematics\u00a021, 281\u2013297 (1984)","journal-title":"Annals of Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,10]],"date-time":"2019-03-10T21:24:52Z","timestamp":1552253092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}