1 Introduction 1
1.1 Background and motivation 1
1.2 Intersection graphs and interval graphs 4
1.3 Tolerance graphs： definitions and examples 5
1.4 Chordal， comparability， interval graphs 7
1.5 Ordered sets 13
1.6 The hierarchy of permutation， parallelogram， trapezoid，function and AT-free graphs 15
1.7 Other families of graphs 20
1.8 Other reading and general references 24
1.9 Exercises 25
2 Early work on tolerance graphs 29
2.1 Notation and observations 29
2.2 Permutation graphs and interval graphs 31
2.3 Bounded tolerance graphs 33
2.4 Tolerance graphs are weakly chordal 36
2.5 Tolerance graphs are perfect 40
2.6 A first look at unit vs.proper 45
2.7 Classes of perfect graphs 48
2.8 Exercises 52
3 Trees， cotrees and bipartite graphs 53
3.1 Trees and cotrees 53
3.2 Bipartite tolerance graphs - the bounded case 60
3.3 Exercises 61
4 Interval probe graphs and sandwich problems 63
4.1 Physical mapping of DNA 63
4.2 Interval probe graphs 65
4.3 The hierarchy of interval， probe， and tolerance graphs 66
4.4 The trees that are interval probe graphs 71
4.5 Partitioned interval probe graphs 73
4.6 The enhancement of a partitioned probe graph is chordal 74
4.7 The Interval Graph Sandwich Problem 77
4.8 The NP-completeness of the Interval Probe Graph Sandwich Problem 80
4.9 Exercises 82
5 Bitolerance and the ordered sets perspective 84
5.1 The concept of a bounded tolerance order 84
5.2 Classes of bounded bitolerance orders 85
5.3 Geometric interpretations 91
5.4 Exercises 96
6 Unit and 50% tolerance orders 98
6.1 Unit tolerance orders with six or fewer elements 98
6.2 Unit vs.proper for bounded bitolerance orders 103
6.3 Width 2 bounded tolerance orders 107
6.4 Exercises 108
7 Comparability invariance results 109
7.1 Comparability invariance 109
7.2 Autonomous sets and Gallai’s Theorem 111
7.3 Dimension is a comparability invariant 112
7.4 Bounded tolerance orders 113
7.5 Unit bitolerance and unit tolerance orders 115
7.6 Exercises 122
8 Recognition of bounded bitolerance orders and trapezoid graphs 124
8.1 Preliminaries 125
8.2 The order B（I） of extreme corners 127
8.3 The isomorphism between B（P） and B（I*） 130
8.4 The recognition algorithm and its complexity 132
8.5 Exercises 133
9 Algorithms on tolerance graphs 135
9.1 Tolerance and bounded tolerance representations 136
9.2 Coloring tolerance representations 137
9.3 Maximum weight stable set of a tolerance representation 140
9.4 Exercises 144
10 The hierarchy of classes of bounded bitolerance orders 146
10.1 Introduction 146
10.2 Equivalent classes 148
10.3 Bipartite orders 152
10.4 Separating examples 158
10.5 Exercises 163
11 Tolerance models of paths and subtrees of a tree 164
11.1 Introduction 164
11.2 Intersection models 164
11.3 Discrete models 165
11.4 Neighborhood subtrees 169
11.5 Neighborhood subtree tolerance （NeST） graphs 173
11.6 Subclasses of NeST graphs 176
11.7 The hierarchy of NeST graphs 183
11.8 A connection with threshold and threshold tolerance graphs 187
11.9 Exercises 191
12 φ-tolerance graphs 193
12.1 Introduction 193
12.2 φ-tolerance chain graphs 195
12.3 Archimedean φ-tolerance graphs 201
12.4 Polynomial functions 209
12.5 Every graph can be represented by an Archimedean polynomial 210
12.6 Construction of a universal Archimedean tolerance function 213
12.7 Unit and proper representations 215
12.8 Exercises 217
13 Directed tolerance graphs 219
13.1 Ferrers dimension 2 220
13.2 Bounded bitolerance digraphs 222
13.3 Recognition of bounded bitolerance digraphs 224
13.4 Characterizations of bounded bitolerance digraphs 225
13.5 The digraph hierarchy 228
13.6 Cycles 234
13.7 Trees 237
13.8 Unit vs.proper 243
13.9 Exercises 248
14 Open questions and further directions of research 249
References 253
Index of symbols 260
Index 262