# 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.

• This is equivalent to asking whether a graph has an odd-hole; currently this is open. Polynomial-time algorithms are known for special classes of graphs; also there is a structural result about the odd-hole-free graphs. Jan 30 '14 at 17:49
• Thank you for quick reply.Are there any similar (Like strong perfect graph theorem) result for graphs which are not subclass of perfect graphs ? Jan 30 '14 at 17:53

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