Bounded bitolerance digraphs (Q1974515)

A loopless directed graph \(\vec{G} = (V, A)\) is a bounded bitolerance digraph if it can be represented as follows. Each vertex \(x\in V\) is assigned a real interval \(I(x) =[le(x), re(x)]\), a left tolerant point \(lt(x)\in I(x)\), and a right tolerant point \(rt(x)\in I(x)\). The left tolerant interval of \(x\) is the interval \([le(x), lt(x))\) and the right tolerant interval of \(x\) is the interval \((rt(x), re(x)]\). For distinct vertices \(x\) and \(y\), we have \((x,y)\in A\) if and only if the intersection \(I(x)\cap I(y)\) is not a subset of either tolerant interval of \(y\). The authors prove: (1) A loopless directed graph \(\vec{G} = (V, A)\) is a bounded bitolerance graph if and only if there exist interval orders \(P_i = (V, <_i)\), \(i= 1,2\), such that \(\widetilde{P_1}\cup\widetilde{P_2} = \vec{G}\), where \(\widetilde{P_i}\) is the directed graph with vertex set \(V\) and arcs \((x,y)\) for all \(x<_i y\) or \(x\) and \(y\) are incomparable in \(P_i\). (2) Let \(\vec{G}\) be a loopless symmetric directed graph, i.e. if \((x,y)\) is an arc of \(\vec{G}\) then is also \((y,x)\). Then \(\vec{G}\) is a bounded bitolerance graph if and only if the underlying graph \(G\) of \(\vec{G}\) is an interval graph. The authors also discuss bounded bitolerance graphs \(\vec{G}\) such that \(\vec{G} = \widetilde{P_1}\cup \widetilde{P_2}\) for certain restricted interval orders \(P_i\).