<p>Please check the following article: 
C.G. Lekkerkerker and J.C. Boland, Representations of a finite graph by a set of intervals on the line, Fund. Math. 45-64 (1962)</p>

<p>In this article, authors cite all the forbidden subgraphs to an interval graph thus a proper interval graph. The forbidden subgraphs are the following: 
 - a bipartite claw; 
 - n-net, n>=2; 
 - umbrella; 
 - n-tent, n>=3; 
 - Cn, n>=4.</p>

CC BY-SA 3.0
2016-08-06T16:22:02.413Z
Could you please expand the answer a little bit, summarizing how the article cited answers the question?
chazisop
CC BY-SA 3.0
2016-08-06T22:49:30.777Z
@chazisop, I've just edited my answer. I hope it'd help.
Gunelle
CC BY-SA 3.0
2016-08-06T11:31:48.670Z
2016-08-06T22:49:06.167Z
2016-08-06T22:49:06.167Z
Gunelle
<p><a href="http://www.graphclasses.org/classes/gc_298.html" rel="nofollow noreferrer" title="ISCI&#39;s page on proper interval graphs">ISGCI's page on proper interval graphs</a> (from our <a href="https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science">FAQ</a>) lists a few equivalent classes; one of them is the class of $(C_{n+4}$, $S_3$, claw, net)-free  graphs (see the same website for definitions).</p>

CC BY-SA 3.0
2017-08-28T12:08:03.680Z
These same forbidden graphs are also depicted in an illustration of the Wikipedia article on proper interval graphs, en.wikipedia.org/wiki/Proper_interval_graph
David Eppstein
CC BY-SA 3.0
2014-02-13T07:36:13.040Z
2014-02-13T07:36:13.040Z
2017-03-16T15:45:13.547Z
Anthony Labarre
<p>A graph is an interval graph iff it is chordal and asteroidal triple free.
An interval graph is proper interval graph iff it is $K_{1,3}$ free.</p>

<p>However i googled intensely to find a minimal set of forbidden subgraphs for proper interval graphs,but in vain.</p>

<p>My question is : What are the minimal set of forbidden subgraphs for proper interval graphs ?
Any link to journal/paper is welcome.</p>

<graph-theory><graph-algorithms><interval-graphs>
Forbidden subgraph characterisation of interval graphs
Dibyayan
# Forbidden subgraph characterisation of interval graphs

(Asked by: username_0 on 2014-02-13)

A graph is an interval graph iff it is chordal and asteroidal triple free.
An interval graph is proper interval graph iff it is $K\_{1,3}$ free.

However i googled intensely to find a minimal set of forbidden subgraphs for proper interval graphs,but in vain.

My question is : What are the minimal set of forbidden subgraphs for proper interval graphs ?
Any link to journal/paper is welcome.

**Tags:** graph-theory, graph-algorithms, interval-graphs


---

## 2 answers

### Answer by username_3 on 2014-02-13. Score: 8 | Accepted answer

[ISGCI's page on proper interval graphs](http://www.graphclasses.org/classes/gc_298.html "ISCI's page on proper interval graphs") (from our [FAQ](https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science)) lists a few equivalent classes; one of them is the class of $(C\_{n+4}$, $S\_3$, claw, net)-free graphs (see the same website for definitions).

> **Comments:**
> **username_4**: These same forbidden graphs are also depicted in an illustration of the Wikipedia article on proper interval graphs, en.wikipedia.org/wiki/Proper_interval_graph  

---

### Answer by username_1 on 2016-08-06. Score: 2

Please check the following article:
C.G. Lekkerkerker and J.C. Boland, Representations of a finite graph by a set of intervals on the line, Fund. Math. 45-64 (1962)

In this article, authors cite all the forbidden subgraphs to an interval graph thus a proper interval graph. The forbidden subgraphs are the following:
- a bipartite claw;
- n-net, n>=2;
- umbrella;
- n-tent, n>=3;
- Cn, n>=4.

> **Comments:**
> **username_2**: Could you please expand the answer a little bit, summarizing how the article cited answers the question?  
> **username_1**: @username_2, I've just edited my answer. I hope it'd help.  

---

