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?

$\endgroup$
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.

$\endgroup$
  • 1
    $\begingroup$ I wish I give more than one up vote for this $\endgroup$ – Tyson Williams Aug 4 '11 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 '11 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 '11 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 '11 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.

$\endgroup$

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.