6
$\begingroup$

I was confused by Wikipedia's definitions of "chordal graph", "interval graph", "string graph", "comparability graph", "incomparability graph" and the complements of these. Wikipedia says "The complement of any interval graph is a comparability graph". So is any chordal graph an incomparability graph?

Is there a book or survey that contains detailed description of these sorts of different perfect graphs?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
24
$\begingroup$

I believe the answer to your question, and to most questions like this, is to be found on http://graphclasses.org/

There's also a book that has much of this (including an appendix at the back with some of the main subset relations between graph classes): Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.

The answer to your specific question is no. The graph shown in http://commons.wikimedia.org/wiki/File:SubdividedTriangle.png (a central triangle with three more triangle attached to its edges) is chordal, but its complement http://en.wikipedia.org/wiki/File:Forbidden_interval_subgraph.svg is not a comparability graph.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I wish I give more than one up vote for this $\endgroup$
    – Tyson Williams
    Aug 4, 2011 at 15:42
  • $\begingroup$ Actually, I am not so sure about this website any more. Their server has an error if you try to suggest new graph classes. You are then instructed to email their webmaster at webmaster@graphclasses.org but that email address doesn't exist. $\endgroup$
    – Tyson Williams
    Aug 4, 2011 at 16:18
  • $\begingroup$ @Tyson: perhaps try emailing Ernst De Ridder, hnridder at informatik.uni-rostock.de which used to be the address to email before the move to the new domain. $\endgroup$
    – András Salamon
    Aug 6, 2011 at 15:52
  • $\begingroup$ Posing on half of Ernst de Ridder: I'd like to apologize for the email problems at graphclasses.org. Both the feedback form and the webmaster email address should now work again. Please note that my old Rostock University address as given by Andras doesn't work anymore. I can be reached these days at hnridder at graphclasses.org. Bring on those emails with new classes! :-) $\endgroup$
    – Tyson Williams
    Aug 12, 2011 at 13:25
2
$\begingroup$

A book source for information about problems of this type is: Graph Classes: A Survey, A. Brandstadt, Le, and Spinrad, SIAM, 1999.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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