Tolerance graphs, and orders
Stefan Felsner · Journal of Graph Theory · 1998
We show that, if a tolerance graph is the complement of a comparability graph, it 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 that is alternatingly orientable but not a tolerance graph. We also characterize the tolerance graphs among complements of trees. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 129–140, 1998