Perfect graphs

• Includes an introduction by Claude Berge, the founder of perfect graph theory
• Discusses the most recent developments in the field of perfect graph theory
• Provides a thorough historical overview of the subject
• Internationally respected authors highlight the new directions, seminal results and the links the field has with other subjects
• Discusses how semi-definite programming evolved out of perfect graph theory The early developments of the theory are included to lay the groundwork for the later chapters.

Contents

• List of Contributors.
• Preface.
• Acknowledgements.
• Origins and Genesis (C. Berge and J.L. Ramirez Alfonsin).
• Perfection.
• Communication Theory.
• The Perfect Graph Conjecture.
• Shannon's Capacity.
• Translation of the Halle-Wittenberg Proceedings.
• Indian Report.
• References.
• From Conjecture to Theorem (Bruce A Reed).
• Gallai's Graphs.
• The Perfect Graph Theorem.
• Some Polyhedral Consequences.
• A Stronger Theorem.
• References.
• A Translation of Gallai's Paper: "Transitiv Orientierbare Graphen" (Frederic Maffray and Myriam Preissmann).
• Translators' Foreword.
• References.
• Even Pairs (Hazel Everett et al).
• Introduction.
• Even Pairs and Perfect Graphs.
• Perfectly Contractile Graphs.
• Quasi-parity Graphs.
• Recent Progress.
• Odd Pairs.
• References.
• The P4-Structure of Perfect Graphs (Stefan Hougardy).
• Introduction.
• P4-Stucture: Basics, Isomorphisms and Recognition.
• Modules, h-Sets, Split Graphs and Unique P4-Structure.
• The Semi-Strong perfect Graph Theorem.
• The Structure of the P4-Isomorphism Classes.
• Recognizing P4-Structure.
• The P4-Structure of Minimally Imperfect Graphs.
• The Partner Structure and Other Generalizations.
• P3-Structure.
• References.
• Forbidding Holes and Antiholes (Ryan Hayward and Bruce A. Reed).
• Introduction.
• Graphs with No Holes.
• Graphs with No Discs.
• Graphs with No Long Holes.
• Balanced Matrices.
• Bipartitie Graphs with No Hole of Length 4k + 2.
• Graphs without Even Holes.
• &b.beta; -Perfect Graphs.
• Graphs without Odd Holes.
• References.
• Perfectly Orderable Graphs: A Survey (Chinh T Hoang).
• Introduction.
• Classical Graphs.
• MinimalNonperfectly Orderable Graphs.
• Orientations.
• Generalizations of Triangulated Graphs.
• Generalizations of Complements of Chordal Bipartitie Graphs.
• Other Classes of Perfectly Orderable Graphs.
• Vertex Orderings.
• Generalizations of Perfectly Orderable Graphs.
• Optimizing Perfectly Ordered Graphs.
• References.
• Cutsets in Perfect and Minimal Imperfect Graphs (Irena Rusu).
• Introduction.
• How Did It Start?
• Main Results on Minimal Imperfect Graphs.
• Applications: Star Cutsets.
• Applications: Clique and Multipartite Cutsets.
• Applications: Stable Cutsets.
• Two (Resolved) Conjectures.
• The Connectivity of Minimal Imperfect Graphs.
• Some (More) Problems.
• References.
• Some Aspects of Minimal Imperfect Graphs (Myriam Preissmann and Andras Sebo).
• Introduction.
• Imperfect and Partitionable Graphs.
• Properties.
• Constructions.
• References.
• Graph Imperfection and Channel Assignment (Colin McDiarmid).
• Introduction.
• The Imperfection Ratio.
• An Alternative Definition.
• Further Results and Questions.
• background on Channel Assignment.
• References.
• A Gentle Introduction to Semi-definite Programming (Bruce A. Reed).
• Introduction.
• The Ellipsoid Method.
• Solving Semi-definite Programs.
• Randomized Rounding and Derandomization.
• Approximating MAXCUT.
• Approximating Bandwidth.
• Graph Colouring.
• The Theta Body.
• References.
• The Theta Body and Imperfection (F.B. Shepherd).
• Background and Overview.
• Optimization, Convexity and Geometry.
• The Theta Body.
• Partitionable Graphs.
• Perfect Graph Characterizations and a Continuous Perfect Graph Conjecture.
• References.
• Perfect Graphs and Graph Entropy (Gabor Simonyi).
• Introduction.
• The Information-Theoretic Interpretation.
• Some Basic Properties.
• Structural Theorems: Relation to Perfectness.
• Applications.
• Generalizations.
• Graph Capacities and Other Related Functionals.
• References.
• A Bibliography on Perfect Graphs (Vasek Chvatal).
• Index.