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.
Recommended Citation
Bogart, K. P.,
Jacobson, M. S.,
McMorris, F. R.,
&
Langley, L. L.
(2001).
Tolerance orders and bipartite unit tolerance graphs.
Discrete Mathematics, 226(1--3), 35–50.
DOI: 10.1016/S0012-365X(00)00124-2
https://scholarlycommons.pacific.edu/cop-facarticles/636
