Talk:Interval graph

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Are the intervals elements of R as stated, or of (R,R)?

--SimonFunk 01:33, 17 February 2006 (UTC)[reply]

Complement of interval graphs

Is it true that complements of interval graphs are comparability graphs ? It seems that comparability graphs are the complement of co-comparability graphs, and that interval graphs are the intersection of chordal graphs and co-comparability graphs. 193.55.49.19 (talk) 13:14, 18 September 2008 (UTC)[reply]

That's what I interpret the article to mean. The sentence “Interval graphs are chordal graphs and hence perfect graphs” doesn't mean that these three graph classes are equal, it means only that the interval graphs are a subset of the chordal graphs which are a subset of the perfect graphs. Similarly, the sentence “Their complements are comparability graphs” doesn't mean that these two classes are equal, it means only that the complements of interval graphs are a subset of the compariability graphs. Perhaps this could be worded more unambiguously. The equivalence between interval graphs and (chordal intersect co-comparability) is mentioned in ISGCI. —David Eppstein (talk) 15:20, 18 September 2008 (UTC)[reply]

Ok, it's clear for me now. Thank you very much, Pr. Eppstein. 82.67.69.152 (talk) 23:02, 20 September 2008 (UTC)[reply]