<p>There is a structural result for odd-hole-free graphs by Michele Conforti, Gérard Cornuéjols, and Kristina Vušković:</p>

<blockquote>
  <p><a href="http://www.sciencedirect.com/science/article/pii/S0166218X03003640">Decomposition of odd-hole-free graphs by double star cutsets and 2-joins</a>, Discrete Applied Mathematics, 2004.</p>
</blockquote>

<p>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.  </p>

<p>The interesting thing is that although <a href="http://www.sciencedirect.com/science/article/pii/S0095895612000810">the structural theorem of even-hole-free graphs</a> leads to polynomial-time recognition algorithms (<a href="http://integer.tepper.cmu.edu/webpub/algo-even.pdf">1</a>, <a href="http://arxiv.org/abs/1311.0358">2</a>), the corresponding implication is not known for odd-hole-free graphs.  However if we add the restriction that the clique number is bounded then <a href="http://integer.tepper.cmu.edu/webpub/oddhole2.pdf">we do have such a result</a>.</p>

<hr>

<p>$^1$ The first decomposition-based algorithm.
$^2$ The fastest algorithm currently known.</p>

CC BY-SA 3.0
2014-01-30T20:46:45.803Z
2014-01-30T20:46:45.803Z
Hsien-Chih Chang 張顯之
<p>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. </p>

CC BY-SA 3.0
2014-01-30T17:49:01.180Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-01-30T17:53:37.850Z
Thank you for quick reply.Are there any similar (Like strong perfect graph theorem) result for graphs which are not subclass of perfect graphs ?
Dibyayan
<graph-theory>
Criteria to determine if a complement of a graph has odd-holes
Dibyayan
# Criteria to determine if a complement of a graph has odd-holes

(Asked by: username_0 on 2014-01-30)

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.

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: Thank you for quick reply.Are there any similar (Like strong perfect graph theorem) result for graphs which are not subclass of perfect graphs ?  

---

## 1 answers

### Answer by username_1 on 2014-01-30. Score: 10

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](http://www.sciencedirect.com/science/article/pii/S0166218X03003640), 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](http://www.sciencedirect.com/science/article/pii/S0095895612000810) leads to polynomial-time recognition algorithms ([1](http://integer.tepper.cmu.edu/webpub/algo-even.pdf), [2](http://arxiv.org/abs/1311.0358)), 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](http://integer.tepper.cmu.edu/webpub/oddhole2.pdf).

---

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


---

