Perfect graphs / edited by Jorge L. Ramírez Alfonsin, Bruce A. Reed.

Format:

Book

Contributor:

Ramírez Alfonsin, Jorge L.

Reed, Bruce A.

Series:

Wiley-Interscience series in discrete mathematics and optimization

Language:

English

Subjects (All):

Perfect graphs.

Physical Description:

xxii, 362 pages : illustrations ; 26 cm.

Place of Publication:

Chichester ; New York : Wiley, [2001]

Summary:

Perfect graph theory was born out of a conjecture about graph colouring made by Claude Berge in 1960. That conjecture remains unsolved, but it has generated an important area of research in combinatorics. In this first book on the subject, the authors bring together all the questions, methods and ideas of perfect graph theory, and highlight the new methods and applications generated by Berge's conjecture. Discusses the most recent developments in the field of perfect graph theory.

Highlights applications in frequency assignments for telecommunications systems, integer programming and optimization.

Discusses how semi-definite programming evolved out of perfect graph theory.

Includes an introduction by Claude Berg. Features internationally respected authors. Primarily of interest to researchers from mathematics, combinatorics, computer science and telecommunications, the book will also appeal to students of graph theory.

Contents:

1 Origins and Genesis / C. Berge, J.L. Ramirez Alfonsin 1

1.1 Perfection 1

1.2 Communication Theory 1

1.3 The Perfect Graph Conjecture 3

1.4 Shannon's Capacity 7

1.5 Translation of the Halle-Wittenberg Proceedings 7

1.6 Indian Report 10

2 From Conjecture to Theorem / Bruce A. Reed 13

2.1 Gallai's Graphs 14

2.2 The Perfect Graph Theorem 16

2.3 Some Polyhedral Consequences 18

2.4 A Stronger Theorem 22

3 A Translation of Gallai's Paper: 'Transitiv Orientierbare Graphen' / Frederic Maffray, Myriam Preissmann 25

3.1 Introduction and Results 26

3.2 The Proofs of Theorems (3.1.2), (3.1.5) and (3.1.6) 34

3.3 The proofs of (3.1.8) and (3.1.9) 38

3.4 The Proof of (3.1.16) 40

3.5 The Proof of (3.1.17) 44

3.6 Determination of All Irreducible Graphs 47

3.7 Determination of the Irreducible Graphs 56

4 Even Pairs / Hazel Everett, Celina M. H. de Figueiredo, Claudia Linhares Sales, Frederic Maffray, Oscar Porto, Bruce A. Reed 67

4.2 Even Pairs and Perfect Graphs 70

4.3 Perfectly Contractile Graphs 72

4.3.1 Weakly Triangulated Graphs 72

4.3.2 Meyniel Graphs 73

4.3.3 Perfectly Orderable Graphs 75

4.3.4 Other Classes of Perfectly Contractile Graphs 77

4.3.5 Graphs that Might Be Perfectly Contractile 78

4.3.6 Forbidden Subgraphs in Perfectly Contractile Graphs 78

4.4 Quasi-parity Graphs 80

4.4.1 Characterization of QP and SQP Graphs 82

4.5 Recent Progress 83

4.5.1 Planar Graphs 84

4.5.2 Claw-Free Graphs 85

4.5.3 Bull-Free Graphs 86

4.5.4 Diamond-Free Graphs 87

4.6 Odd Pairs 88

5 The P[subscript 4]-Structure of Perfect Graphs / Stefan Hougardy 93

5.2 P[subscript 4]-Structure: Basics, Isomorphisms and Recognition 94

5.3 Modules, h-Sets, Split Graphs and Unique P[subscript 4]-Structure 96

5.4 The Semi-Strong Perfect Graph Theorem 101

5.5 The Structure of the P[subscript 4]-Isomorphism Classes 102

5.6 Recognizing P[subscript 4]-Structure 105

5.7 The P[subscript 4]-Structure of Minimally Imperfect Graphs 106

5.8 The Partner Structure and Other Generalizations 107

5.9 P[subscript 3]-Structure 108

6 Forbidding Holes and Antiholes / Ryan Hayward, Bruce A. Reed 113

6.2 Graphs with No Holes 114

6.3 Graphs with No Discs 116

6.4 Graphs with No Long Holes 120

6.5 Balanced Matrices 121

6.6 Bipartite Graphs with No Hole of Length 4k + 2 122

6.6.1 Some Preliminary Remarks 124

6.6.2 Clean Holes 125

6.6.3 A Recognition Algorithm 126

6.6.4 A Fresh Look at Cleanliness 127

6.6.5 Recognizing Balanceable Graphs 129

6.7 Graphs without Even Holes 130

6.7.1 The Decomposition Theorem 131

6.8 [beta]-Perfect Graphs 132

6.9 Graphs without Odd Holes 133

7 Perfectly Orderable Graphs: A Survey / Chinh T. Hoang 139

7.2 Classical Graphs 140

7.2.1 Triangulated Graphs 141

7.2.2 Chordal Bipartite Graphs and Gamma-Free Matrices 141

7.2.3 Comparability Graphs 141

7.2.4 Interval Graphs 142

7.3 Minimal Nonperfectly Orderable Graphs 142

7.4.1 Six Classes of Perfectly Orderable Graphs 144

7.4.2 Opposition Orientation 146

7.5 Generalizations of Triangulated Graphs 147

7.5.1 Quasi-triangulated Graphs 147

7.5.2 Brittle Graphs 148

7.5.3 Quasi-brittle Graphs 149

7.5.4 C-orientation 149

7.6 Generalizations of Complements of Chordal Bipartite Graphs 149

7.6.1 Claw-Free Graphs 149

7.6.2 P[subscript 5]-Free Weakly Triangulated Graphs 150

7.6.3 Bull-Free Perfectly Orderable Graphs 151

7.6.4 D-Graphs 151

7.7 Other Classes of Perfectly Orderable Graphs 152

7.7.1 Complements of Tolerance Graphs 152

7.7.2 Strongly Perfectly Orderable Graphs 152

7.7.3 Charming Graphs 153

7.7.4 Nice Graphs 153

7.7.5 Bipartable Graphs 153

7.7.6 Intersection and Union of Two Threshold Graphs 153

7.7.7 P[subscript 4] Composition 156

7.8 Vertex Orderings 156

7.8.1 Lexicographic Breadth-First Search 157

7.8.2 Maximal Cardinality Search 158

7.8.3 Orders by Degrees 158

7.9 Generalizations of Perfectly Orderable Graphs 159

7.9.1 Quasi-perfectly Orderable Graphs 160

7.9.2 Properly Orderable Graphs 160

7.9.3 Perfectly Orientable Graphs 161

7.10 Optimizing Perfectly Ordered Graphs 161

8 Cutsets in Perfect and Minimal Imperfect Graphs / Irena Rusu 167

8.2 How Did It Start? 168

8.3 Main Results on Minimal Imperfect Graphs 169

8.4 Applications: Star Cutsets 172

8.5 Applications: Clique and Multipartite Cutsets 174

8.6 Applications: Stable Cutsets 176

8.7 Two (Resolved) Conjectures 178

8.8 The Connectivity of Minimal Imperfect Graphs 179

9 Some Aspects of Minimal Imperfect Graphs / Myriam Preissmann, Andras Selbo 185

9.1.2 Classifications of the Results 188

9.1.3 Polyhedra 189

9.1.4 Testing Imperfectness and Partitionability 189

9.2 Imperfect and Partitionable Graphs 191

9.2.1 Basic properties 191

9.2.2 Small Certificate for Imperfectness 193

9.2.3 Small Certificates for Partitionable Graphs 194

9.3 Properties 195

9.3.1 Partitionable and Minimal Imperfect Graphs 195

9.3.2 Genuine properties 197

9.4 Constructions 207

9.4.1 Generalities 207

9.4.2 Partitionable Graphs with Circular Symmetry 209

9.4.3 Adding a Critical Clique 210

10 Graph Imperfection and Channel Assignment / Colin McDiarmid 215

10.2 The Imperfection Ratio 217

10.3 Alternative Definitions 219

10.4 Further Results and Questions 220

10.4.1 List Colouring 220

10.4.2 Triangle-Free Planar Graphs 221

10.4.3 Imperfection and Odd Holes 221

10.4.4 Dilation Ratio 222

10.4.5 Graph Entropy 223

10.4.6 Random Graphs 224

10.4.7 Extremal behaviour 225

10.4.8 Hardness 225

10.4.9 Lexicographic Products 225

10.4.10 Values of imp(G) 225

10.4.11 Holes and Antiholes 226

10.4.12 Binary Imperfection Ratio 226

10.4.13 Circular Arc Graphs 226

10.4.14 Unit Disc Graphs 227

10.5 Background on Channel Assignment 227

11 A Gentle Introduction to Semi-definite Programming / Bruce A. Reed 233

11.2 The Ellipsoid Method 235

11.2.1 How the Algorithm Works 237

11.2.2 Solving LPs 239

11.3 Solving Semi-definite Programs 241

11.4 Randomized Rounding and Derandomization 244

11.4.1 The Method of Conditional Expectation for MAXSAT 245

11.4.2 Randomized Rounding 246

11.4.3 A Combined Approach 247

11.4.4 Random Projection 248

11.5 Approximating MAXCUT 248

11.6 Approximating Bandwidth 250

11.6.1 The First Algorithm 250

11.6.2 A More Sophisticated Algorithm 252

11.7 Graph Colouring 252

11.7.1 Colouring Perfect Graphs 252

11.7.2 Colouring 3-Colourable Graphs 254

11.8 The Theta Body 256

12 The Theta Body and Imperfection / F.B.

Shepherd 261

12.1.1 Perfection and Integer Programming 261

12.1.2 Imperfection and Partitionability 262

12.1.4 Partitionability and Branch and Cut Methods for Packing Problems 266

12.2 Optimization, Convexity and Geometry 267

12.2.1 Convexity and Encoding Conventions 268

12.2.2 Optimization over a Convex Body: Consequences of the Ellipsoid Method 269

12.2.3 The Discovery Problem 270

12.3 The Theta Body 272

12.3.1 Three Convex Bodies 272

12.3.2 A Semi-definite Formulation 273

12.3.3 Algorithms for the Theta Body 275

12.3.4 Additive Gap Guarantees and the Protrusion of the Theta Body 276

12.4 Partitionable Graphs 280

12.4.1 A Characterization 280

12.4.2 A Recognition Algorithm 283

12.5 Perfect Graph Characterizations and a Continuous Perfect Graph Conjecture 285

13 Perfect Graphs and Graph Entropy / Gabor Simonyi 293

13.2 The Information-Theoretic Interpretation 295

13.3 Some Basic Properties 297

13.3.1 Monotonicity 297

13.3.2 Sub-additivity 298

13.3.3 Additivity of substitution 298

13.4 Structural Theorems: Relation to Perfectness 300

13.4.1 Additivity for Complementary Pairs 300

13.4.2 Imperfection Ratio 302

13.4.3 Additivity for Arbitrary Pairs 304

13.4.4 Sub- and Supermodular Pairs 306

13.4.5 Weak Additivity and Normality 307

13.5 Applications 309

13.5.1 Kahn and Kim's Application for Sorting 309

13.5.2 About Other Applications 310

13.6 Generalizations 312

13.6.1 Hypergraph Entropy 312

13.6.2 Additivity for Complementary Uniform Hypergraphs 312

13.6.3 Entropy of Convex Corners 315

13.6.4 Job Scheduling Application 315

13.7 Graph Capacities and Other Related Functionals 316

13.7.1 Shannon Capacity 316

13.7.2 Sperner Capacity 319

13.7.3 Probabilistic Lovasz Function 321

13.7.4 Co-entropy 323

14 A Bibliography on Perfect Graphs / Vasek Chvatal 329.

Notes:

Includes bibliographical references and index.

ISBN:

0471489700

OCLC:

46640717

Online:

Table of Contents