On a problem concerning tolerance graphs (Q689957)

A tolerance graph is defined as an undirected graph \(G\) with the property that to each vertex \(x\) of \(G\) an interval \(I_ x\) on the real line and a positive number \(t_ x\) can be assigned in such a way that two vertices \(x\), \(y\) are adjacent in \(G\) if and only if the length of the interval \(I_ x \cap I_ y\) is greater than or equal to \(\min(t_ x,t_ y)\). If moreover \(t_ x\) is less than or equal to the length of \(I_ x\) for each vertex \(x\) of \(G\), then \(G\) is called a bounded tolerance graph. For a complement of a tree it is proved that it is a tolerance graph if and only if it is a bounded tolerance graph. This is a particular case of a conjecture by M. C. Golumbic, C. L. Monma and W. T. Trotter. Moreover, a complement of a tree being a tolerance graph is characterized by means of a forbidden subgraph.