This is an encyclopedic survey on theoretical and algorithmic results on
graph classes. In a sense, this work is a follow-up on [M.C. Golumbic,
Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980;
MR 81e:68081], which appeared in 1980. Since that time, the field has grown
substantially. This well-written survey covers over 200 classes of graphs.
Results are stated without proofs. This book will help researchers in this
field to keep track of the literature, and the descriptions of the connections
between graph classes should be useful to them. The book contains 14 chapters
that are summarized below.
Chapter 1 introduces concepts such as chordal graphs and their associated
hypergraphs, partially ordered sets (posets), and modular decomposition.
Chapter 2 introduces perfect graphs and their generalizations. Chapter 3
discusses the concept of chords in graphs and surveys results on strongly
chordal, chordal bipartite and bridged graphs. Chapter 4 discusses intersection
graphs (graphs that are intersection graphs of combinatorial objects) such as
line-graphs, interval graphs, circular arc graphs and visibility graphs of
polygons.
Chapter 5 surveys results on vertex and edge orderings. It discusses the
well-known perfect elimination scheme and its generalizations, the perfect
orders, and the cop-win orderings. Chapter 6 covers the connection between
posets and graphs. Chapter 7 surveys results on graphs that are defined by
forbidden subgraphs such as cographs (P4-free graphs), claw-free graphs and
hole-free graphs. There is also a discussion on planar graphs. Chapter 8
discusses results on hypergraphs. It introduces the concepts of cycles of
hypergraphs, hypertrees, normal hypergraphs and interval hypergraphs.
Chapter 9 surveys results on matrices and polyhedra. For example, it covers
the consecutive 1's property of the clique matrix of interval graphs, balance
and totally balanced matrices, perfect matrices, and the eigenvalues of the
adjacency matrices of graphs. Chapter 10 surveys results on the distance
properties of graphs. Among the topics covered are distance-hereditary graphs,
interval conditions, convexity, and powers of graphs. Chapter 11 covers k-trees,
series-parallel graphs, cographs and their generalizations, and recursively
defined perfect graphs (perfect graphs that are constructed by operations such
as clique-bonding or the amalgam operation).
Chapter 12 discusses methods of decomposing a graph into subgraphs such as modular
decomposition, split decomposition, and clique cutset decomposition. The chapter
also discusses minimal separators and the planar separator theorem. Chapter 13
surveys results on threshold graphs. Chapter 14 surveys results on the strong
perfect graph conjecture.
It should be noted that two books have been written on the subjects of Chapters 4 and 13 [T.A. McKee and F.R. McMorris, Topics in intersection graph theory, SIAM, Philadelphia, PA, 1999; MR 20 00e:05001; N.V.R. Mahadev and U.N. Peled, Threshold graphs and related topics, Ann. Discrete Math., 56, North-Holland, Amsterdam, 1995; MR 97h:05001]. This survey, however, offers a panoramic view of the world of graph classes and the connections between them, and therefore is highly recommended by this reviewer.