In the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices.
Addario-Berry et al. (2008) demonstrated that every even-hole-free graph contains a bisimplicial vertex, which settled a conjecture by Reed.
Recognition
Conforti et al. (2002) gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in
While even-hole-free graphs can be recognized in polynomial time, it is NP-complete to determine whether a graph contains an even hole that includes a specific vertex.