Research Seminar
a graph contains an odd hole. Later that year, Chudnovsky, Scott and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least [...] parity of its length. In 1991, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole a predetermined vertex of G. In 2002, Conforti, Cornuéjols, Kapoor and Vušković gave a polyn
