Technical Report 309-1991

Title

Tolerance Graphs and Orders

Author

Stefan Felsner

Publication

Springer, Lecture Notes in Computer Science No. 657, ed. E.W. Mayr, 1993, pp. 17-26

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

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.