TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

Tolerance Graphs and Orders
Citation key Report-309-1991
Author Stefan Felsner
Title of Book Lecture Notes in Computer Science No.\ 657, 1993
Pages 17-26
Year 1991
Number 309
Editor E.W. Mayr
Publisher Springer-Verlag
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe