{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T10:45:08Z","timestamp":1784544308753,"version":"3.55.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T00:00:00Z","timestamp":1580256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Leverhulme Trust Research Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1763817 (Chudnovsky), DMS-1800053 (Seymour), and DMS-1802201 (Spirkl)"],"award-info":[{"award-number":["DMS-1763817 (Chudnovsky), DMS-1800053 (Seymour), and DMS-1802201 (Spirkl)"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["A9550-19-1-0187 (Seymour)"],"award-info":[{"award-number":["A9550-19-1-0187 (Seymour)"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000183","name":"U. S. Army Research Office","doi-asserted-by":"crossref","award":["W911NF-16-1-0404 (Chudnovsky)"],"award-info":[{"award-number":["W911NF-16-1-0404 (Chudnovsky)"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"<jats:p>We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd.<\/jats:p>","DOI":"10.1145\/3375720","type":"journal-article","created":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T11:10:47Z","timestamp":1580296247000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Detecting an Odd Hole"],"prefix":"10.1145","volume":"67","author":[{"given":"Maria","family":"Chudnovsky","sequence":"first","affiliation":[{"name":"Princeton University, Princeton NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[{"name":"Mathematical Institute, University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Seymour","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2536-5618","authenticated-orcid":false,"given":"Sophie","family":"Spirkl","sequence":"additional","affiliation":[{"name":"Rutgers University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,1,29]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"114","article-title":"F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind","volume":"10","author":"Berge Claude","year":"1961","unstructured":"Claude Berge . 1961 . F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind . Wiss. Z. 10 (1961), 114 -- 111 . Claude Berge. 1961. F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. 10 (1961), 114--11.","journal-title":"Wiss. Z."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90098-M"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90357-L"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/060672613"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1384263.1384264"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"e_1_2_1_8_1","volume-title":"Testing for a long odd hole. arXiv preprint arXiv:1904.12273","author":"Chudnovsky Maria","year":"2019","unstructured":"Maria Chudnovsky , Alex Scott , and Paul Seymour . 2019. Testing for a long odd hole. arXiv preprint arXiv:1904.12273 ( 2019 ). Maria Chudnovsky, Alex Scott, and Paul Seymour. 2019. Testing for a long odd hole. arXiv preprint arXiv:1904.12273 (2019)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.07.005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1380579.1380582"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1932"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582135"},{"key":"e_1_2_1_13_1","volume-title":"Testing for a long even hole. in preparation","author":"Cook Linda","year":"2019","unstructured":"Linda Cook and Paul Seymour . 2019. Testing for a long even hole. in preparation ( 2019 ). Linda Cook and Paul Seymour. 2019. Testing for a long even hole. in preparation (2019)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4064\/am-19-3-4-413-441"},{"key":"e_1_2_1_15_1","volume-title":"Three-in-a-tree in near linear time. arXiv preprint arXiv:1909.07446","author":"Lai Kai-Yuan","year":"2019","unstructured":"Kai-Yuan Lai , Hsueh- I Lu , and Mikkel Thorup . 2019. Three-in-a-tree in near linear time. arXiv preprint arXiv:1909.07446 ( 2019 ). Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup. 2019. Three-in-a-tree in near linear time. arXiv preprint arXiv:1909.07446 (2019)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.10.002"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375720","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375720","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:15Z","timestamp":1750199895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,29]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3375720"],"URL":"https:\/\/doi.org\/10.1145\/3375720","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,29]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}