Bipartite tolerance orders

AbstractTolerance orders and tolerance graphs arise as a generalization of interval orders and interval graphs in which some overlap of intervals is tolerated. The classes of bounded, proper and unit tolerance orders and graphs have been studied by other authors. Here we introduce two-sided versions of these classes. We show that all the classes are identical for bipartite ordered sets and give some examples to show that the classes differ in the nonbipartite case. We also give an algorithm for determining whether a bipartite ordered set is in these classes, and if so finding a representation of it