TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1993

Tolerance Graphs and Orders
Zitatschlüssel Report-309-1991
Autor Stefan Felsner
Buchtitel Lecture Notes in Computer Science No.\ 657, 1993
Seiten 17-26
Jahr 1991
Nummer 309
Herausgeber E.W. Mayr
Verlag Springer-Verlag
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We show that a tolerance graph that is the complement of a comparability graph is a trapezoid graph, i.e., the complement of an order of interval dimension at most 2. As consequences we are able to give obstructions for the class of bounded tolerance graphs and to give an example of a graph which is alternatingly orientable but not a tolerance graph. We also characterize the tolerance graphs among the complements of trees.
Typ der Publikation Preprint
Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe