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

Golumbic, Martin Charles

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.

Reviewer: Haiko Müller (Leeds)

MSC:

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

Keywords:

perfect graph; triangulated graph; chordal graph; comparability graph; split graph; permutation graph; interval graph; threshold graph; circle graph; chordal bipartite graph; intersection graph; efficient algorithm

Citations:

Zbl 0541.05054