@article{7debeb7e003f4984b000830f34a1d682,
title = "Odd holes in bull-free graphs∗ ",
abstract = "The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).",
keywords = "Algorithm, Bull-free, Odd hole",
author = "Maria Chudnovsky and Vaidy Sivaraman",
note = "Funding Information: ∗Received by the editors May 22, 2017; accepted for publication (in revised form) February 26, 2018; published electronically April 26, 2018. http://www.siam.org/journals/sidma/32-2/M113130.html Funding: The first author was partially supported by NSF grant DMS-1550991 and by U.S. Army Research Office grant W911NF-16-1-0404. †Department of Mathematics, Princeton University, Princeton, NJ 08544 (mchudnov@math. princeton.edu). ‡Department of Mathematical Sciences, Binghamton University, Binghamton, NY 13902 (vaidy@ math.binghamton.edu). Publisher Copyright: {\textcopyright} 2018 Society for Industrial and Applied Mathematics.",
year = "2018",
doi = "10.1137/17M1131301",
language = "English (US)",
volume = "32",
pages = "951--955",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",
}