  A hole in a graph G is an induced cycle of length at least four; an antihole
is a hole in the complement of G. In 2005, Chudnovsky, Cornuejols, Liu, Seymour
and Vuskovic showed that it is possible to test in polynomial time whether a
graph contains an odd hole or antihole (and thus whether G is perfect).
However, the complexity of testing for odd holes has remained open. Indeed, it
seemed quite likely that testing for an odd hole was NP-complete: for instance,
Bienstock showed that testing if a graph has an odd hole containing a given
vertex is NP-complete. In this paper we resolve the question, by giving a
polynomial-time algorithm to test whether a graph contains an odd hole. This
also gives a new and considerably simpler polynomial-time algorithm that tests
for perfection.
