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).

  • $\begingroup$ 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 $\endgroup$ – 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.

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

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.