<p>In fact, it is relatively easy. Instead for studying independent set problem in (odd-hole,antihole)-free graphs, we take complement of the graphs and try to find a maximum clique in it. Thus it becomes maximum clique problem in (hole, anti-odd-hole)-free graphs.</p>

<p>In section 2 of the paper "<a href="http://www.comp.leeds.ac.uk/murilo/ehf.pdf">Triangulated Neighborhoods in Even-hole-free Graphs</a>" by da Silva and Vuskovic, they stated that Farber first shows </p>

<blockquote>
  <p>There are $O(n^2)$ maximal cliques in any 4-hole free graphs.</p>
</blockquote>

<p>Then their main theorem stated that</p>

<blockquote>
  <p>There are $O(n + m)$ maximal cliques in even-hole-free graphs, and all the maximal cliques can be found in time $O(n^2m)$.</p>
</blockquote>

<p>Since we are dealing with (hole, anti-odd-hole)-free graphs which is clearly even-hole-free, finding a maximum clique takes at most $O(n^2m)$ time.</p>

<p>4-hole-free are critical to these kind of results like a poly-time algorithm for $\overline{K_{2,m}}$-free graphs, so the real challenge may be studying independent set problem in (hole, anti-odd-hole)-free graphs instead, which becomes the maximum clique problem in (odd-hole, anti-hole)-free graphs.</p>

<hr>

<p>Edit:</p>

<p>Oh, another thought came out. (hole, anti-odd-hole)-free graphs are almost weakly chordal in the following sense: since 4-hole-free implies there are only anti-holes with size 4~7 remains (any k-anti-hole with size > 7 contains a 4-hole), and it is also anti-odd-hole-free which restrict the size of anti-holes down to 4 and 6, it is almost no holes/antiholes in the graph! Thus a poly-time algorithm seems plausible for such graphs.</p>

CC BY-SA 3.0
2012-07-10T18:56:39.420Z
@AndrásSalamon can you give open access to preprints of your work on this topic? I couldn't access through my university's proxy neither
didest
CC BY-SA 3.0
2012-07-13T14:17:32.203Z
@DiegodeEstrada: I'd be happy to send you a preprint of our CP 2008 paper, just send me an email.  However, it really is a constraints paper so may not be that interesting to you.
András Salamon
CC BY-SA 2.5
2010-10-28T15:50:15.213Z
The overline runs away, there I mean the complement of $K_{2,m}$ for any $m\geq 2$.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-29T09:23:53.257Z
Thanks!  Looking again at my result with Peter Jeavons, we actually showed that tree-structured constraint problems yield (hole, odd-antihole)-free graphs in which one wants to find the largest independent set.  I will make the question more precise -- I incorrectly suggested IS was the problem one wanted to solve.
András Salamon
CC BY-SA 2.5
2010-10-28T15:48:10.830Z
2010-10-28T16:01:48.210Z
2010-10-28T16:01:48.210Z
Hsien-Chih Chang 張顯之
<p>X-free graphs are those that contain no graph from X as an induced subgraph.  A <em>hole</em> is a cycle with at least 4 vertices.  An <em>odd-hole</em> is a hole with an odd number of vertices.  An <em>antihole</em> is the complement of a hole.</p>

<p>The (odd-hole,odd-antihole)-free graphs are precisely the perfect graphs; this is the <a href="http://dx.doi.org/10.4007%2Fannals.2006.164.51">Strong Perfect Graph Theorem</a>.  It is possible to find the largest independent set <em>(and largest clique)</em> in a perfect graph in polynomial time, but the only known method of doing so requires building a semi-definite program to compute the <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_number">Lovász theta number</a>.</p>

<p>The (hole,antihole)-free graphs are called <em><a href="http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_14.html">weakly chordal</a></em>, and constitute a rather easy class for many problems (including INDEPENDENT SET <em>and CLIQUE</em>).</p>

<blockquote>
  <p>Does anyone know if (odd-hole,antihole)-free graphs have been studied or written about?</p>
</blockquote>

<p>These graphs occur quite naturally in constraint satisfaction problems where the graph of related variables forms a tree.  Such problems are rather easy, so it would be nice if there were a way to find a largest <strike>independent set</strike> <em>clique</em> for graphs in this family without having to compute the Lovász theta.</p>

<p><em>Equivalently, one wants to find a largest independent set for (hole, odd-antihole)-free graphs.  Hsien-Chih Chang points out below why this is a more interesting class for INDEPENDENT SET than (odd-hole, antihole)-free graphs.</em></p>

<reference-request><graph-theory><co.combinatorics><graph-classes>
Reference for (odd-hole,antihole)-free graphs?
András Salamon
# Reference for (odd-hole,antihole)-free graphs?

(Asked by: username_0 on 2010-10-28)

X-free graphs are those that contain no graph from X as an induced subgraph. A *hole* is a cycle with at least 4 vertices. An *odd-hole* is a hole with an odd number of vertices. An *antihole* is the complement of a hole.

The (odd-hole,odd-antihole)-free graphs are precisely the perfect graphs; this is the [Strong Perfect Graph Theorem](http://dx.doi.org/10.4007%2Fannals.2006.164.51). It is possible to find the largest independent set *(and largest clique)* in a perfect graph in polynomial time, but the only known method of doing so requires building a semi-definite program to compute the [Lovász theta number](http://en.wikipedia.org/wiki/Lov%C3%A1sz_number).

The (hole,antihole)-free graphs are called *[weakly chordal](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_14.html)*, and constitute a rather easy class for many problems (including INDEPENDENT SET *and CLIQUE*).

> Does anyone know if (odd-hole,antihole)-free graphs have been studied or written about?

These graphs occur quite naturally in constraint satisfaction problems where the graph of related variables forms a tree. Such problems are rather easy, so it would be nice if there were a way to find a largest independent set *clique* for graphs in this family without having to compute the Lovász theta.

*Equivalently, one wants to find a largest independent set for (hole, odd-antihole)-free graphs. Hsien-Chih Chang points out below why this is a more interesting class for INDEPENDENT SET than (odd-hole, antihole)-free graphs.*

**Tags:** reference-request, graph-theory, co.combinatorics, graph-classes


---

## 1 answers

### Answer by username_1 on 2010-10-28. Score: 12

In fact, it is relatively easy. Instead for studying independent set problem in (odd-hole,antihole)-free graphs, we take complement of the graphs and try to find a maximum clique in it. Thus it becomes maximum clique problem in (hole, anti-odd-hole)-free graphs.

In section 2 of the paper "[Triangulated Neighborhoods in Even-hole-free Graphs](http://www.comp.leeds.ac.uk/murilo/ehf.pdf)" by da Silva and Vuskovic, they stated that Farber first shows

> There are $O(n^2)$ maximal cliques in any 4-hole free graphs.

Then their main theorem stated that

> There are $O(n + m)$ maximal cliques in even-hole-free graphs, and all the maximal cliques can be found in time $O(n^2m)$.

Since we are dealing with (hole, anti-odd-hole)-free graphs which is clearly even-hole-free, finding a maximum clique takes at most $O(n^2m)$ time.

4-hole-free are critical to these kind of results like a poly-time algorithm for $\overline{K\_{2,m}}$-free graphs, so the real challenge may be studying independent set problem in (hole, anti-odd-hole)-free graphs instead, which becomes the maximum clique problem in (odd-hole, anti-hole)-free graphs.

---

Edit:

Oh, another thought came out. (hole, anti-odd-hole)-free graphs are almost weakly chordal in the following sense: since 4-hole-free implies there are only anti-holes with size 4~7 remains (any k-anti-hole with size > 7 contains a 4-hole), and it is also anti-odd-hole-free which restrict the size of anti-holes down to 4 and 6, it is almost no holes/antiholes in the graph! Thus a poly-time algorithm seems plausible for such graphs.

> **Comments:**
> **username_1**: The overline runs away, there I mean the complement of $K_{2,m}$ for any $m\geq 2$.  
> **username_0**: Thanks!  Looking again at my result with Peter Jeavons, we actually showed that tree-structured constraint problems yield (hole, odd-antihole)-free graphs in which one wants to find the largest independent set.  I will make the question more precise -- I incorrectly suggested IS was the problem one wanted to solve.  
> **username_2**: @AndrásSalamon can you give open access to preprints of your work on this topic? I couldn't access through my university's proxy neither  
> **username_0**: @DiegodeEstrada: I'd be happy to send you a preprint of our CP 2008 paper, just send me an email.  However, it really is a constraints paper so may not be that interesting to you.  

---

