Tolerance graphsPDF电子书下载

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