CONTENTS
Graph Classes: A Survey

Preface ix

Chapter 1: Basic Concepts 1

• 1.1 Basic graph notions 1
• 1.2 Chordal graphs 6
• 1.3 Basic hypergraph notions and properties 7
• 1.4 Partial orders 11
• 1.5 Modular decomposition 13
• 1.6 Some basic algorithms and problems 15
• 1.7 Some special graphs 17

Chapter 2: Perfection, Generalized Perfection and Related Concepts 21

• 2.1 Perfect graphs and perfect graph theorems 21
• 2.2 A semi-strong perfect graph theorem 24
• 2.3 Sharpening perfection 28
• 2.4 Properties of perfect graphs 29
• 2.5 Generalized perfection 31
• 2.6 Related concepts 34

Chapter 3: Cycles, Chords and Bridges 39

• 3.1 $(k,l)$-chordal graphs 39
• 3.2 Chordality conditions for $G$ and $\overline G$ 40
• 3.3 Cycles and chords in bipartite graphs 41
• 3.4 Odd chords 43
• 3.5 Meyniel graphs, subclasses and variants 44
• 3.6 Bridged graphs and isometric cycles 45

Chapter 4: Models and Interactions 47

• 4.1 Basic concepts 47
• 4.2 Line graphs and generalizations 48
• 4.3 Interval graphs and variants 50
• 4.4 Tree models and variants 52
• 4.5 Boxicity, intersection dimension and dot product 54
• 4.6 Circular arc graphs 55
• 4.7 Permutation, circle and trapezoid graphs and similar concepts 56
• 4.8 Measured intersection 60
• 4.9 Other geometric objects 63
• 4.10 Other interactions - visibility 64

Chapter 5: Vertex and Edge Orderings 67

• 5.1 Perfect elimination and generalizations 67
• 5.2 Semiperfect elimination 70
• 5.3 Domination and distance-preserving elimination 72
• 5.4 Maximum neighborhood orderings and generalizations 74
• 5.5 Strong and simple orderings and generalizations 76
• 5.6 Perfect orderings 80
• 5.7 Special perfectly orderable graphs 81
• 5.8 Cop-win orderings 87
• 5.9 Edge elimination orderings 88

Chapter 6: Posets 91

• 6.1 Partial orders and their graphs 91
• 6.2 Poset dimension 92
• 6.3 Containment graphs 94
• 6.4 Series-parallel posets 96
• 6.5 Interval orders and semiorders 96
• 6.6 Arborescence orders and threshold orders 99
• 6.7 Comparability graphs with other restrictions 100
• 6.8 Posets and diagrams 101

Chapter 7: Forbidden Subgraphs 105

• 7.1 Finitely many forbidden induced subgraphs 105
  • 7.1.1 One forbidden induced subgraph 105
  • 7.1.2 $P_4$, $C_4$, $2K_2$ and other subgraphs 106
  • 7.1.3 $C_5$, $P_5$, $\overline P_5 $, $C_6$, $\overline C_6 $, $P_6$, $\overline P_6 $ and other subgraphs 107
  • 7.1.4 $K_ 1,3 $ and other subgraphs 109
  • 7.1.5 Other examples 111
• 7.2 Infinitely many forbidden induced subgraphs 112
  • 7.2.1 Comparability graphs and variants 112
  • 7.2.2 Chordality and suns 112
  • 7.2.3 Hole-free graphs and variants 113
  • 7.2.4 Asteroidal triples 114
• 7.3 Forbidden minors - planarity and variants 116
• 7.4 Forbidden induced ordered subgraphs 119

Chapter 8: Hypergraphs and Graphs 123

• 8.1 $\alpha $-acyclicity of hypergraphs 123
• 8.2 Further acyclicity types and clique and neighborhood hypergraphs 125
• 8.3 Graphs with maximum neighborhood orderings and corresponding hypertrees 127
• 8.4 Further classes with dual hypertree characterizations 130
• 8.5 Disk-Helly, clique-Helly, and neighborhood-Helly graphs 131
• 8.6 Perfect graphs and normal hypergraphs 133
• 8.7 Interval hypergraphs 134

Chapter 9: Matrices and Polyhedra 135

• 9.1 The consecutive 1s and the circular 1s property 135
• 9.2 Balanced and totally balanced matrices and doubly lexical orderings 137
• 9.3 Perfect and totally unimodular matrices 139
• 9.4 Birkhoff graphs and doubly stochastic matrices 141
• 9.5 Forbidden sets of submatrices 142
• 9.6 Eigenvalues and graphs 143

Chapter 10: Distance Properties 147

• 10.1 Distance-hereditary and parity graphs 147
• 10.2 Subclasses of distance-hereditary graphs 149
  • 10.2.1 Cographs 149
  • 10.2.2 Bipartite distance-hereditary graphs 149
  • 10.2.3 Chordal distance-hereditary graphs 150
  • 10.2.4 Block graphs and related classes 151
• 10.3 Interval conditions 152
• 10.4 Absolute retracts of reflexive and bipartite graphs 155
• 10.5 Convexity 157
• 10.6 Powers of graphs 161

Chapter 11: Algebraic Compositions and Recursive Definitions 167

• 11.1 Trees, $k$-trees and partial $k$-trees 167
• 11.2 Series-parallel graphs 172
• 11.3 Cographs and domination 175
  • 11.3.1 Cograph characterizations 175
  • 11.3.2 Domination properties 175
• 11.4 Bounding the number of $P_4$s 177
  • 11.4.1 $P_4$-reducible and $P_4$-sparse graphs and variants 177
  • 11.4.2 $p$-trees 179
  • 11.4.3 $(q,t)$-graphs 180
• 11.5 Tree-cographs and hookup classes 181
• 11.6 Recursively defined perfect graphs 182

Chapter 12: Decompositions and Cutsets 187

• 12.1 Modular decomposition - the poset aspect 187
• 12.2 Homogeneous decomposition 189
• 12.3 Split decomposition 191
• 12.4 Other decompositions 192
• 12.5 Minimal separators 194
• 12.6 Classes with polynomially bounded number of minimal separators 194
• 12.7 Clique, biclique and stable cutsets 195
• 12.8 Small and balanced separators 197

Chapter 13: Threshold Graphs and Related Concepts 199

• 13.1 The threshold dimension 199
• 13.2 Constant-bounded Dilworth number 201
• 13.3 Degree sequences 203
• 13.4 Matroidal and matrogenic graphs 204

Chapter 14: The Strong Perfect Graph Conjecture 207

• 14.1 Properties of minimal imperfect graphs 208
• 14.2 Some equivalent versions of the SPGC 213
• 14.3 Large classes of perfect graphs 214
• 14.4 Graph classes satisfying the SPGC 217
  • 14.4.1 $F$-free graphs 217
  • 14.4.2 Graph-valued functions and intersection models 218
  • 14.4.3 Other graph classes 219
• 14.5 Two semi-strong perfect graph conjectures 221
• 14.6 The weakened strong perfect praph conjecture 222

Appendix A: Recognition 223

Appendix B: Containment Relationships 229

Bibliography 251

Index 293

Back to Graph Classes Survey homepage