×

On the hierarchy of interval, probe and tolerance graphs. (English) Zbl 0995.05104

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.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite