Tolerance orders and bipartite unit tolerance graphs

Document Type

Article

Publication Title

Discrete Mathematics

Department

Mathematics

ISSN

0012-365X

Volume

226

Issue

1--3

DOI

10.1016/S0012-365X(00)00124-2

First Page

35

Last Page

50

Publication Date

1-6-2001

Abstract

We construct all six-element orders which are not 50%-tolerance orders. We show that a width-two order is a 50% tolerance order if and only if no restriction of the order to a six-element set is isomorphic to one of these six-element orders. This yields a corresponding characterization of bipartite 50%-tolerance graphs. Since an order (graph) has a 50% tolerance representation if and only if it has a unit tolerance representation, our results apply to unit tolerance orders (graphs) as well.

Link to Full Text

Share

COinS