Talk:Interval graph

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]

Optimal Coloring Complexity

I proposed an edit to the introduction that was rolled back, so I'm hoping to gain some insight on this topic. If there's a linear-time algorithm given an interval graph that produces an optimal coloring, I'd be interested to learn more about it. From my investigation so far, I have found only linear complexity from greedy coloring when provided with a pre-computed elimination ordering; however, unless I'm mistaken, the process of finding that ordering would increase time complexity.

Further along in the article, there's a brief discussion about using the greedy approach to color the graph in polynomial time, which seems in tension with the introduction. Additionally, the pages on both chordal graphs and perfect graphs note polynomial time complexity for optimal coloring. If there's a resource describing such a linear-time algorithm, I think it would be worth including the citation in the article or at least mentioning it in the graph coloring section. Imma pepper (talk) 01:35, 20 July 2024 (UTC)[reply]

Infact, I believe I was mistaken!

The ordering can be found in linear-time as well for chordal graphs, an important insight which I missed. I still think it would be valuable content to include in the article(s), but I concede the point and apologize for the erroneous contribution. Imma pepper (talk) 07:32, 20 July 2024 (UTC)[reply]