More precisely, the definition may allow the graph to have induced cycles of length four, or may also disallow them: the latter is referred to as even-cycle-free graphs.
[1] Addario-Berry et al. (2008) demonstrated that every even-hole-free graph contains a bisimplicial vertex (a vertex whose neighborhood is the union of two cliques), which settled a conjecture by Reed.
Conforti et al. (2002b) gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in
The best currently known algorithm is given by Lai, Lu & Thorup (2020) 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.
[3] It is unknown whether graph coloring and the maximum independent set problem can be solved in polynomial time on even-hole-free graphs, or whether they are NP-complete.
However the maximum clique can be found in even-hole-free graphs in polynomial time.