Criteria to determine if a complement of a graph has odd-holes Is there any graph theoretic result for recognising graphs whose complement has no odd holes ?
I know about perfect graphs but they have the extra criteria being odd-hole free.
There is a structural result for odd-hole-free graphs by Michele Conforti, Gérard Cornuéjols, and Kristina Vušković:


  Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, Discrete Applied Mathematics, 2004.


Basically what it says is either the odd-hole-free graph belongs to a kind of basic class, or we can decompose the graph into smaller pieces using two kinds of decompositions.  The proof of the strong perfect graph theorem follows the same spirit, and similar results are also known for various classes, e.g. even-hole-free graphs.  

The interesting thing is that although the structural theorem of even-hole-free graphs leads to polynomial-time recognition algorithms (1, 2), the corresponding implication is not known for odd-hole-free graphs.  However if we add the restriction that the clique number is bounded then we do have such a result.



$^1$ The first decomposition-based algorithm.
$^2$ The fastest algorithm currently known.