Perfect Graphs (Hardcover)

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.

Table of Contents

List of Contributors.

Preface.

Acknowledgements.

1. Origins and Genesis (C. Berge and J.L. Ramirez Alfonsin).

2. From Conjecture to Theorem (Bruce A Reed).

3. A Translation of Gallai's Paper: "Transitiv Orientierbare Graphen" (Frederic Maffray and Myriam Preissmann).

4. Even Pairs (Hazel Everett et al).

5. The P₄-Structure of Perfect Graphs (Stefan Hougardy).

6. Forbidding Holes and Antiholes (Ryan Hayward and Bruce A. Reed).

7. Perfectly Orderable Graphs: A Survey (Chinh T Hoang).

8. Cutsets in Perfect and Minimal Imperfect Graphs (Irena Rusu).

9. Some Aspects of Minimal Imperfect Graphs (Myriam Preissmann and Andras Sebo).

10. Graph Imperfection and Channel Assignment (Colin McDiarmid).

11. A Gentle Introduction to Semi-definite Programming (Bruce A. Reed).

12. The Theta Body.

13. Perfect Graphs and Graph Entropy (Gabor Simonyi).

14 A Bibliography on Perfect Graphs (Va&sbreve;ek Chvátal).

Index.