4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 30 '14 at 17:49
  • $\begingroup$ Thank you for quick reply.Are there any similar (Like strong perfect graph theorem) result for graphs which are not subclass of perfect graphs ? $\endgroup$ – Dibyayan Jan 30 '14 at 17:53
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.