Tolerance graphs, and orders (Q4242964)

An undirected graph \(G=(V,E)\) is defined to be a tolerance graph if there exists a collection \({\mathcal I}=\{I_x\mid x\in V\}\) of closed intervals on the line and a (tolerance) function \(t:V\to\mathbb{R}^+\) satisfying \((x,y)\in E\) iff \(| I_x\cap I_y|\geq\min(t_x,t_y)\), where \(| I|\) denotes the length of the interval \(I\). Such a graph is a bounded tolerance graph if it admits a tolerance representation \(\{{\mathcal I},t\}\) with \(| I_x |\geq t_x\) for all \(x\in V\), and a graph \(G\) is called alternatingly orientable if there is an orientation of \(G\) such that around every chordless cycle of length greater than 3 the directions of arcs alternate. In the present paper the author essentially gets the following results: (1) Every tolerance graph that is the complement of a comparability graph (a so-called cocomparability graph) is the complement of an order of interval dimension at most 2 (a so-called trapezoid graph). This is a consequence of Theorem 4 of the paper. (2) Tolerance graphs are alternatingly orientable (which is a consequence of already known structural properties of tolerance graphs in Theorem 2). (3) Vice versa the author shows by an example that a graph admitting an alternating orientation must not be a tolerance graph. (4) A necessary and sufficient condition for a graph to be a bounded tolerance graph is given (Theorem 3), and obstructions for the classes of tolerance graphs and bounded tolerance graphs are also given (by Theorems 6 and 7). (5) Complements of trees \(T\) (so-called cotrees \(\overline T)\) are cocomparability graphs. They are characterized in Theorem 5 by some equivalent conditions, for example, \(\overline T\) is a tolerance graph, \(\overline T\) is a bounded tolerance graph, \(\overline T\) is a trapezoid graph.