# Forbidden subgraph characterisation of interval graphs

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.

ISGCI's page on proper interval graphs (from our FAQ) 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).

• 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 Aug 28 '17 at 12:08

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.

• Could you please expand the answer a little bit, summarizing how the article cited answers the question? – chazisop Aug 6 '16 at 16:22
• @chazisop, I've just edited my answer. I hope it'd help. – Gunelle Aug 6 '16 at 22:49