zbMATH — the first resource for mathematics

Tolerance graphs. (English) Zbl 1091.05001
Cambridge Studies in Advanced Mathematics 89. Cambridge: Cambridge University Press (ISBN 0-521-82758-2/hbk). xii, 265 p. (2004).
An idea of the scope of this work can be obtained by listing the chapter headings: Early work on tolerance graphs; Trees, cotrees, and bipartite graphs; Interval probe graphs and sandwich problems; Bitolerance and the ordered sets perspective; Unit and 50% tolerance orders; Comparability invariance results; Bounded bitolerance orders and trapezoid graphs; Algorithms on tolerance graphs; Hierarchy of classes of bounded bitolerance orders; Tolerance models of paths and subtrees of a tree; Phi-tolerance graphs; Directed tolerance graphs; Open questions and further directions of research.
Tolerance graphs were introduced in 1982 by M. C. Golumbic and C. L. Monma [Congr. Numerantium 35, 321–331 (1982; Zbl 0537.05062)] in order to solve scheduling problems associated with interval graphs. Since that time, the two authors of this book have been among the most active researchers in the area, and they have produced a thorough survey of major known properties of tolerance graphs. The book will be of great value to researchers in the field, and it can also be used as a graduate text in graph theory, since many examples and exercises have been included.

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05Cxx Graph theory