Tolerance orders and bipartite unit tolerance graphs (Q1841895)

Let \(G= (V,E)\) be a finite graph and \(\phi\) a symmetric positive real-valued function with domain \(R^+\times R^+\). Then \(G\) is a \(\phi\)-tolerance interval graph if it has a \(\phi\)-tolerance interval representation which means that each vertex \(x\in V\) is assigned an interval \(I_x\) on the real line and a tolerance \(t_x\) satisfying: \(xy\in E\) if and only if \(|I_x\cap I_y|\geq \phi(t_x, t_y)\) (where \(|I|\) is the length of the interval \(I\)). A unit tolerance graph is a min-tolerance graph which has a representation using intervals of equal length. A 50\% tolerance graph is a tolerance graph with a representation by intervals \(I_x\) with tolerance \(t_x=|I_x|/2\). The corresponding order defined on the complement of a 50\% tolerance graph is called a 50\% tolerance order. In this paper, the authors construct all six-element orders which are not 50\% tolerance orders. They 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 characterization of bipartite 50\% tolerance graphs. These results apply to unit tolerance orders (graphs) as well.