Talk:Interval graph

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority 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 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

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

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