Algorithmic graph theory and perfect graphs. 2nd ed. (English) Zbl 1050.05002

Annals of Discrete Mathematics 57. Amsterdam: Elsevier (ISBN 0-444-51530-5/hbk). xxvi, 314 p. (2004).
M. C. Golumbic’s book has now become the classic introduction to graph classes characterised by intersection models or elimination orderings. The first edition [Algorithmic graph theory and perfect graphs (Computer Science and Applied Mathematics; New York etc.: Academic Press. A Subsidiary of Harcourt Brace Jovanovich, Publishers. XX) (1980; Zbl 0541.05054)] consists of 12 chapters entitled graph theoretic foundations, the design of efficient algorithms, perfect graphs, triangulated graphs (also known as chordal graphs), comparability graphs, split graphs, permutation graphs, interval graphs, superperfect graphs, threshold graphs, not so perfect graphs (circle graphs), perfect Gaussian elimination, and an appendix. The second edition presents this material in exactly the same way. Additionally it contains a foreword 2004, a list of corrections and an epilogue 2004. The latter mentions the strong perfect graph theorem and classes of graphs that attained attention after 1980, among them strongly and weakly chordal graphs, cographs, asteroidal triple-free graphs, tolerance graphs, and circular-arc graphs as well as algorithms processing graphs in these classes.


05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C62 Graph representations (geometric and intersection representations, etc.)
05C15 Coloring of graphs and hypergraphs
05C17 Perfect graphs
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68W99 Algorithms in computer science


Zbl 0541.05054