joint work with Henry Martyn Mulder, Econometrisch Institut, Erasmus Universiteit Rotterdam
A graph G = (V,E) is a tolerance graph with tolerance t provided there is a map v --> Sv from the vertex set V of G into subtrees of a tree T such that vertices v and w are adjacent in G iff the representing subtrees Sv and Sw have at least t nodes in common. The tree T will be called the host tree for the representation. By a now classical result of Gavril, the tolerance t=1 graphs are precisely the chordal graphs (graphs with no induced cycles of length 4 or more). It is easy to see that every graph G is a tolerance t = 2 graph.
This might appear to be the end of the story, but it turns out that by placing certain restrictions on either the host tree or the representing subtrees, a very rich theory arises. The classical case is that in which the host tree is required to be a path. Then the representable graphs (for any tolerance) are the interval graphs. Although many restrictions are possible, among the simplest and most natural are degree restrictions. Specifically, we shall call v --> Sv an (h,s,t)-representation provided the maximum degree of the host tree T is at most h, every representing subtree Sv has maximum degree at most s, and the tolerance is t. The class of all (h,s,t)-representable graphs will be denoted for simplicity by just [h,s,t]. This talk will present examples and discuss recognition and inclusion issues for these classes.