Golumbic, Martin Charles; Lipshteyn, Marina On the hierarchy of interval, probe and tolerance graphs. (English) Zbl 0995.05104 Congr. Numerantium 153, 97-106 (2001). Summary: Tolerance graphs and interval probe graphs are two generalizations of the well-known class of interval graphs. It is known, and easy to show, that every interval graphs is a probe graph (by choosing \(N\) to be empty), and that every probe graph is a tolerance graph. For all three models, we can place additional restrictions of requiring that all intervals be of unit length or that no interval properly contains another. Clearly, a unit representation is also a proper representation, but not conversely. However, it is well known that unit tolerance graphs do not equal proper tolerance graphs, but that unit interval graphs do equal proper interval graphs. One of our results show that unit probe graphs equal proper probe graphs.In this paper, we present the complete hierarchy of all possible subclasses taken from \(\langle\)unit, proper, general\(\rangle\) \(\times\) \(\langle\)interval, probe, tolerance\(\rangle\) and the class of bounded tolerance graphs, together with examples separating different classes. We survey those results which are known and prove those which are new. Cited in 7 Documents MSC: 05C62 Graph representations (geometric and intersection representations, etc.) Keywords:interval graphs; probe graph; tolerance graph; representation; survey PDFBibTeX XMLCite \textit{M. C. Golumbic} and \textit{M. Lipshteyn}, Congr. Numerantium 153, 97--106 (2001; Zbl 0995.05104)