CHAPTER 1 Graph Theoretic Foundations 1
1.Basic Definitions and Notations 1
2.Intersection Graphs 9
3.Interval Graphs—A Sneak Preview of the Notions Coming Up 13
4.Summary 17
Exercises 18
Bibliography 20
CHAPTER 2 The Design of Efficient Algorithms 22
1.The Complexity of Computer Algorithms 22
2.Data Structures 31
3.How to Explore a Graph 37
4.Transitive Tournaments and Topological Sorting 42
Exercises 45
Bibliography 48
CHAPTER 3 Perfect Graphs 51
1.The Star of the Show 51
2.The Perfect Graph Theorem 53
3.p-Critical and Partitionable Graphs 58
4.A Polyhedral Characterization of Perfect Graphs 62
5.A Polyhedral Characterization of p-Critical Graphs 65
6.The Strong Perfect Graph Conjecture 71
Exercises 75
Bibliography 77
CHAPTER 4 Triangulated Graphs 81
1.Introduction 81
2.Characterizing Triangulated Graphs 81
3.Recognizing Triangulated Graphs by Lexicographic Breadth-First Search 84
4.The Complexity of Recognizing Triangulated Graphs 87
5.Triangulated Graphs as Intersection Graphs 91
6.Triangulated Graphs Are Perfect 94
7.Fast Algorithms for the COLORING，CLIQUE， STABLE SET， and CLIQUE-COVER Problems on Triangulated Graphs 98
Exercises 100
Bibliography 102
CHAPTER 5 Comparability Graphs 105
1.Γ-Chains and Implication Classes 105
2.Uniquely Partially Orderable Graphs 109
3.The Number of Transitive Orientations 113
4.Schemes and G-Decompositions—An Algorithm for Assigning Transitive Orientations 120
5.The 1*-Matroid of a Graph 124
6.The Complexity of Comparability Graph Recognition 129
7.Coloring and Other Problems on Comparability Graphs 132
8.The Dimension of Partial Orders 135
Exercises 139
Bibliography 142
CHAPTER 6 Split Graphs 149
1.An Introduction to Chapters 6-8： Interval，Permutation， and Split Graphs 149
2.Characterizing Split Graphs 149
3.Degree Sequences and Split Graphs 152
Exercises 155
Bibliography 156
CHAPTER 7 Permutation Graphs 157
1.Introduction 157
2.Characterizing Permutation Graphs 158
3.Permutation Labelings 160
4.Applications 162
5.Sorting a Permutation Using Queues in Parallel 164
Exercises 168
Bibliography 169
CHAPTER 8 Interal Graphs 171
1.How It All Started 171
2.Some Characterizations of Interval Graphs 172
3.The Complexity of Consecutive l’s Testing 175
4.Applications of Interval Graphs 181
5.Preference and Indifference 185
6.Circular-Arc Graphs 188
Exercises 193
Bibliography 197
CHAPTER 9 Superperfect Graphs 203
1.Coloring Weighted Graphs 203
2.Superperfection 206
3.An Infinite Class of Superperfect Noncom parability Graphs 209
4.When Does Superperfect Equal Comparability？ 212
5.Composition of Superperfect Graphs 214
6.A Representation Using the Consecutive l’s Property 215
Exercises 218
Bibliography 218
CHAPTER 10 Threshold Graphs 219
1.The Threshold Dimension 219
2.Degree Partition of Threshold Graphs 223
3.A Characterization Using Permutations 227
4.An Application to Synchronizing Parallel Processes 229
Exercises 231
Bibliography 234
CHAPTER 11 Not So Perfect Graphs 235
1.Sorting a Permutation Using Stacks in Parallel 235
2.Intersecting Chords of a Circle 237
3.Overlap Graphs 242
4.Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs 244
5.A Graph Theoretic Characterization of Overlap Graphs 248
Exercises 251
Bibliography 253
CHAPTER 12 Perfect Gaussian Elimination 254
1.Perfect Elimination Matrices 254
2.Symmetric Matrices 256
3.Perfect Elimination Bipartite Graphs 259
4.Chordal Bipartite Graphs 261
Exercises 264
Bibliography 266
Appendix 269
A.A Small Collection of NP-Complete Problems 269
B.An Algorithm for Set Union， Intersection，Difference， and Symmetric Difference of Two Subsets 270
C.Topological Sorting： An Example of Algorithm 2.4 271
D.An Illustration of the Decomposition Algorithm 273
E.The Properties P.E.B.， C.B.，（P.E.B.）’，（C.B.）’ Illustrated 273
F.The Properties C， C —， T， T — llustrated 275
Epilogue 2004 277
Index 307