Talk:Interval graph
Latest comment: 15 years ago by 82.67.69.152 in topic Complement of interval graphs
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Are the intervals elements of R as stated, or of (R,R)?
--SimonFunk 01:33, 17 February 2006 (UTC)
Complement of interval graphs edit
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)
- 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)
- Ok, it's clear for me now. Thank you very much, Pr. Eppstein. 82.67.69.152 (talk) 23:02, 20 September 2008 (UTC)