You are previewing Algorithmic Graph Theory and Perfect Graphs, 2nd Edition.
O'Reilly logo
Algorithmic Graph Theory and Perfect Graphs, 2nd Edition

Book Description

Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails.

Table of Contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Copyright page
  5. Dedication
  6. Foreword 2004: The <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="italic">annals</span> edition edition
    1. Publisher Summary
  7. Foreword
    1. Publisher Summary
  8. Preface
    1. Publisher Summary
  9. Acknowledgments
  10. List of symbols
  11. Corrections and errata to: <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="italic">Algorithmic graph theory and perfect graphs</span>, the original 1980 edition, the original 1980 edition
  12. Chapter 1: Graph Theoretic Foundations
    1. Publisher Summary
    2. 1 Basic Definitions and Notations
    3. 2 Intersection Graphs
    4. 3 Interval Graphs—A Sneak Preview of the Notions Coming Up
    5. 4 Summary
    6. EXERCISES
  13. Chapter 2: The Design of Efficient Algorithms
    1. Publisher Summary
    2. 1 The Complexity of Computer Algorithms
    3. Summary
    4. 2 Data Structures
    5. 3 How to Explore a Graph
    6. 4 Transitive Tournaments and Topological Sorting
    7. Exercises
  14. Chapter 3: Perfect graphs
    1. Publisher Summary
    2. 1 The Star of the Show
    3. THE PERFECT GRAPH
    4. 2 The Perfect Graph Theorem
    5. 3 p-Critical and Partitionable Graphs*
    6. 4 A Polyhedral Characterization of Perfect Graphs
    7. 5 A Polyhedral Characterization of p-Critical Graphs
    8. 6 The Strong Perfect Graph Conjecture
    9. Exercises
  15. Chapter 4: Triangulated graphs
    1. Publisher Summary
    2. 1 Introduction
    3. 2 Characterizing Triangulated Graphs
    4. 3 Recognizing Triangulated Graphs by Lexicographic Breadth-First Search
    5. 4 The Complexity of Recognizing Triangulated Graphs
    6. 5 Triangulated Graphs as Intersection Graphs
    7. 6 Triangulated Graphs Are Perfect
    8. 7 Fast Algorithms for the COLORING, CLIQUE, STABLE SET, and CLIQUE-COVER Problems on Triangulated Graphs
    9. EXERCISES
  16. Chapter 5: Comparability graphs
    1. Publisher Summary
    2. 1 Γ-Chains and Implication Classes
    3. 2 Uniquely Partially Orderable Graphs
    4. 3 The Number of Transitive Orientations
    5. 4 Schemes and <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" class="italic">G</span>-Decompositions&#8212;An Algorithm for Assigning Transitive Orientations-Decompositions—An Algorithm for Assigning Transitive Orientations
    6. 5 The Γ*-Matroid of a Graph
    7. 6 The Complexity of Comparability Graph Recognition
    8. 7 Coloring and Other Problems on Comparability Graphs
    9. 8 The Dimension of Partial Orders
    10. Exercises
  17. Chapter 6: Split graphs
    1. Publisher Summary
    2. 1 An Introduction to Chapters 6–8:Interval, Permutation, and Split Graphs
    3. 2 Characterizing Split Graphs
    4. 3 Degree Sequences and Split Graphs
    5. Theorem 6.4 (Havel [1955], Hakimi [1962])
    6. EXERCISES
  18. Chapter 7: Permutation graphs
    1. Publisher Summary
    2. 1 Introduction
    3. 2 Characterizing Permutation Graphs
    4. 3 Permutation Labelings
    5. 4 Applications
    6. 5 Sorting a Permutation Using Queues in Parallel
    7. Exercises
  19. Chapter 8: Interval graphs
    1. Publisher Summary
    2. 1 How It All Started
    3. 2 Some Characterizations of Interval Graphs
    4. 3 The Complexity of Consecutive 1’s Testing
    5. 4 Applications of Interval Graphs
    6. 5 Preference and Indifference
    7. 6 Circular-Arc Graphs
    8. Exercises*
  20. Chapter 9: Superperfect graphs
    1. Publisher Summary
    2. 1 Coloring Weighted Graphs
    3. 2 Superperfection
    4. 3 An Infinite Class of Superperfect Noncomparability Graphs
    5. 4 When Does Superperfect Equal Comparability?
    6. 5 Composition of Superperfect Graphs
    7. 6 A Representation Using the Consecutive 1’s Property
    8. Exercises
  21. Chapter 10: Threshold graphs
    1. Publisher Summary
    2. 1 The Threshold Dimension
    3. 2 Degree Partition of Threshold Graphs
    4. 3 A Characterization Using Permutations
    5. 4 An Application to Synchronizing Parallel Processes
    6. Exercises
  22. Chapter 11: Not So Perfect Graphs
    1. Publisher Summary
    2. 1 Sorting a Permutation Using Stacks in Parallel
    3. 2 Intersecting Chords of a Circle
    4. 3 Overlap Graphs
    5. 4 Fast Algorithms for Maximum Stable Set and Maximum Clique of These Not So Perfect Graphs
    6. 5 A Graph Theoretic Characterization of Overlap Graphs
    7. EXERCISES
  23. Chapter 12: Perfect Gaussian Elimination
    1. Publisher Summary
    2. 1 Perfect Elimination Matrices
    3. 2 Symmetric Matrices
    4. 3 Perfect Elimination Bipartite Graphs
    5. 4 Chordal Bipartite Graphs
    6. Summary
    7. EXERCISES
  24. Appendix
  25. Epilogue 2004
  26. Index