Algorithmic graph theory and perfect graphs. (English) Zbl 0541.05054

Computer Science and Applied Mathematics; New York etc.: Academic Press. A Subsidiary of Harcourt Brace Jovanovich, Publishers. XX, 284 p. $ 45.00 (1980).
Since the introduction of perfect graphs in the early 1960s more than 200 papers have appeared on this subject. Many special classes of perfect graphs have been introduced. Many of them arise quite naturally in real- world applications. The book concentrates on discussing perfect graphs as well as special classes like triangulated graphs, comparability graphs, interval graphs, permutation graphs, split graphs, superperfect graphs, and threshold graphs. Structural properties of these classes are discussed. Furthermore the author shows how these properties can be exploited to construct efficient algorithms for recognizing these graphs and for solving coloring, clique, stable set, and clique-cover problems. Many applications that occur in operations research, computer science, econometric and other areas are included. This excellent book is an important source for applied mathematicians and computer scientists.
Reviewer: P.Brucker


05C99 Graph theory
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C15 Coloring of graphs and hypergraphs
68W99 Algorithms in computer science
68P10 Searching and sorting