2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for describing a general way of finding reference! $\endgroup$ – MariyaKav Jun 6 at 17:03
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ It's interesting that Mirsky's theorem seems to have been proved in 1971, when Berge's result on the perfection of comparability graphs (which really is exactly the same statement, only in graph-theoretic language - and also in French) dates back to 1960... $\endgroup$ – Misha Lavrov Jun 6 at 17:56
  • $\begingroup$ Now that you mention it, I remember Berge's result. Mirsky's paper doesn't include this application.. $\endgroup$ – saulspatz Jun 6 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.