Representations of tolerance graphs

Abstract

This thesis presents research about tolerance graphs. First some of the background of the class of tolerance graphs and closely related graph classes is provided. Important properties like ’weakly chordal’ and representation models (by intervals on the real line, parallelograms in the real plane or parallelepipeds in the 3-dimensional space) are introduced. An overview of standard algorithms on tolerance graphs and related graph classes is given. We contribute an improved version of a criterion of Golumbic, Monma, Trenk about the distinction between bounded and unbounded tolerance graphs. The new criterion can recognize more tolerance graphs as bounded. Furthermore, an explicit construction of tolerance representations of bipartite tolerance graphs is presented. It can serve as a certificate of an already existing recognition algorithm of bipartite tolerance graphs. These representations as well as representations of unit tolerance graphs are shown to be of small size. In other words, there are non-negative integer tolerance representations for graphs of these two classes with a maximal integer in O(n2). For general tolerance graphs, a new bound of n22n is established, which improves the previously known bound of 1 + 5n25n. The new bound is proved to be correct by integer linear programming techniques. These techniques also yield a moderately fast recognition of tolerance graphs with a small number of vertices, although the recognition is NPcomplete.