Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
By whom it was initially shown that the family of comparability graphs is a subclass of perfect graphs? I am a first year math student and i am working on the project with my group mates, at certain point of the "paper" we claim that comparability graphs is a subclass of perfect graphs, however what do we put as a reference? Where it has been proven first?
P.s. I tried to find information online but didn't succeed.
First, you check Wikipedia. Going to https://en.wikipedia.org/wiki/Perfect_graph and clicking on "Families of graphs that are perfect" gives you a list that includes comparability graphs, and a citation for the list: West's Introduction to Graph Theory.
Then, you look in that textbook. The index tells us that comparability graphs are mentioned on pages 228, 231, and 329-31, with a definition on page 228. Two paragraphs down from the definition, we have
5.3.25.* Proposition. (Berge [1960]) Comparability graphs are perfect.
The proposition is followed by a short proof. It would often be acceptable to cite the textbook for this fact (as Wikipedia does), especially if you're citing the textbook for multiple facts, but in this case, we have more information: we can go to Appendix F: References and see the citation
Berge C., Les problèmes de coloration en théorie des graphes. Publ. Inst. Statist. Univ. Paris 9 (1960), 123-160.
And now you have the original source.
A note on consulting a source before you cite it: Wikipedia is not always reliable, so I would not claim that the theorem is proved in West's Introduction to Graph Theory before actually checking what the textbook says. However, West is always reliable, so I would be fine citing the paper above even if you haven't read it, or don't know French.
If you want to be more careful, you should cite the textbook, and mention that it attributes the result to Claude Berge in such-and-such paper. Or, you could read the paper and find the proof there, in which case you're safe - but should still cite both the textbook and the paper, because the textbook might be easier for readers to find.
According to Wikipedia
Every comparability graph is perfect. The perfection of comparability graphs is Mirsky's theorem, and the perfection of their complements is Dilworth's theorem; these facts, together with the perfect graph theorem can be used to prove Dilworth's theorem from Mirsky's theorem or vice versa.
The article doesn't seem to give a reference for Mirsky's theorem, but it's discussed here.
