Proper and unit bitolerance orders and graphs (Q1381846): Difference between revisions

An order \(\prec\) is a tolerance order on a set of vertices if one may assign to each vertex \(x\) an interval \(I_x\) of real numbers and a real number \(t_x\) called a tolerance in such a way that \(x\prec y\) if and only if the overlap of \(I_x\) and \(I_y\) is less than the minimum of \(t_x\) and \(t_y\) and the center of \(I_x\) is less than the center of \(I_y\). An order is a bitolerance order if and only if there are intervals \(I_x\) and real numbers \(t_l(x)\) and \(t_r(x)\) assigned to the vertex \(x\) in such a way that \(x\prec y\) if and only if the overlap of \(I_x\) and \(I_y\) is less than both \(t_r(x)\) and \(t_l(y)\) and the center of \(I_x\) is less than the center of \(I_y\). A tolerance or bitolerance order is said to be bounded if no tolerance is larger than the length of the corresponding interval. A bounded tolerance graph or bitolerance graph is the incomparability graph of a bounded tolerance order or bitolerance order. Such a graph or order is called proper if it has a representation using intervals no one of which is a proper subset of another, and it is called unit if it has a representation using only unit intervals. The authors prove that a bitolerance graph or order is proper if and only if it is a unit.