Even-hole-free graph


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.
demonstrated that every even-hole-free graph contains a bisimplicial vertex, which settled a conjecture by Reed.

Recognition

gave the first polynomial time recognition algorithm for even-hole-free graphs, which runs in time.
later improved this to.
The best currently known algorithm is given by and which runs in time.
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.
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.