Cover -- Half-title -- Series-title -- Title -- Copyright -- Dedication -- Contents -- Chapter dependencies -- Preface -- Chapter 1 Introduction -- 1.1 Background and motivation -- 1.2 Intersection graphs and interval graphs -- 1.3 Tolerance graphs: definitions and examples -- 1.4 Chordal graphs, comparability graphs, and properties of interval graphs -- 1.4.1 Chordal graphs and split graphs -- 1.4.2 Comparability graphs and transitive orientations -- 1.4.3 Interval graphs -- 1.4.4 Unit interval graphs and proper interval graphs -- 1.5 Ordered sets -- 1.5.1 Interval orders -- 1.5.2 Dimension and interval dimension -- 1.6 The hierarchy of permutation, parallelogram, trapezoid, function, and AT-free graphs -- 1.7 Other families of graphs -- 1.7.1 Weakly chordal graphs -- 1.7.2 Strongly chordal graphs -- 1.7.3 Threshold graphs -- 1.8 Other reading and general references -- 1.9 Exercises -- Chapter 2 Early work on tolerance graphs -- 2.1 Notation and observations -- 2.2 Permutation graphs and interval graphs -- 2.3 Bounded tolerance graphs -- 2.4 Tolerance graphs are weakly chordal -- 2.5 Tolerance graphs are perfect -- 2.6 A first look at unit vs. proper -- 2.7 Classes of perfect graphs -- 2.8 Exercises -- Chapter 3 Trees, cotrees and bipartite graphs -- 3.1 Trees and cotrees -- 3.2 Bipartite tolerance graphs - the bounded case -- 3.3 Exercises -- Chapter 4 Interval probe graphs and sandwich problems -- 4.1 Physical mapping of DNA -- 4.2 Interval probe graphs -- 4.3 The hierarchy of interval, probe, and tolerance graphs -- 4.4 The trees that are interval probe graphs -- 4.5 Partitioned interval probe graphs -- 4.6 The enhancement of a partitioned probe graph is chordal -- 4.7 The Interval Graph Sandwich Problem -- 4.8 The NP-completeness of the Interval Probe Graph Sandwich Problem -- 4.9 Exercises.

Chapter 5 Bitolerance and the ordered sets perspective -- 5.1 The concept of a bounded tolerance order -- 5.2 Classes of bounded bitolerance orders -- 5.2.1 Three types of restrictions -- 5.2.2 Equivalent definitions of bounded tolerance -- 5.2.3 Distinct endpoints and tolerant points -- 5.3 Geometric interpretations -- 5.4 Exercises -- Chapter 6 Unit and 50% tolerance orders -- 6.1 Unit tolerance orders with six or fewer elements -- 6.2 Unit vs. proper for bounded bitolerance orders -- 6.3 Width 2 bounded tolerance orders -- 6.4 Exercises -- Chapter 7 Comparability invariance results -- 7.1 Comparability invariance -- 7.2 Autonomous sets and Gallai's Theorem -- 7.3 Dimension is a comparability invariant -- 7.4 Bounded tolerance orders -- 7.5 Unit bitolerance and unit tolerance orders -- 7.6 Exercises -- Chapter 8 Recognition of bounded bitolerance orders and trapezoid graphs -- 8.1 Preliminaries -- 8.1.1 Dimension and realizers -- 8.1.2 Predecessor and successor sets -- 8.2 The order B(I) of extreme corners -- 8.3 The isomorphism between B(P) and B(I∗) -- 8.4 The recognition algorithm and its complexity -- 8.5 Exercises -- Chapter 9 Algorithms on tolerance graphs -- 9.1 Tolerance and bounded tolerance representations -- 9.2 Coloring tolerance representations -- 9.3 Maximum weight stable set of a tolerance representation -- 9.4 Exercises -- Chapter 10 The hierarchy of classes of bounded bitolerance orders -- 10.1 Introduction -- 10.2 Equivalent classes -- 10.3 Bipartite orders -- 10.4 Separating examples -- 10.4.1 The orders 2 + 2 and 3 + 3 -- 10.4.2 The order 3 + 2 -- 10.4.3 The order 4 + 1 -- 10.4.4 The order A -- 10.4.5 The order B -- 10.5 Exercises -- Chapter 11 Tolerance models of paths and subtrees of a tree -- 11.1 Introduction -- 11.2 Intersection models -- 11.3 Discrete models -- 11.4 Neighborhood subtrees.

11.5 Neighborhood subtree tolerance (NeST) graphs -- 11.6 Subclasses of NeST graphs -- 11.6.1 Unit, proper and bounded NeST graphs -- 11.6.2 Constant tolerance NeST graphs -- 11.6.3 NeST containment graphs -- 11.7 The hierarchy of NeST graphs -- 11.8 A connection with threshold and threshold tolerance graphs -- 11.9 Exercises -- Chapter 12 phi-tolerance graphs -- 12.1 Introduction -- 12.2 phi-tolerance chain graphs -- 12.3 Archimedean phi-tolerance graphs -- 12.4 Polynomial functions phi -- 12.5 Every graph can be represented by an Archimedean polynomial -- 12.6 Construction of a universal Archimedean tolerance function -- 12.7 Unit and proper representations -- 12.8 Exercises -- Chapter 13 Directed tolerance graphs -- 13.1 Ferrers dimension 2 -- 13.2 Bounded bitolerance digraphs -- 13.3 Recognition of bounded bitolerance digraphs -- 13.4 Characterizations of bounded bitolerance digraphs -- 13.5 The digraph hierarchy -- 13.6 Cycles -- 13.7 Trees -- 13.7.1 Trees that are bounded bitolerance digraphs -- 13.7.2 Trees that are unit/proper bitolerance digraphs -- 13.8 Unit vs. proper -- 13.9 Exercises -- Chapter 14 Open questions and further directions of research -- References -- Index of symbols -- Index.