The flavor of this texbook is perhaps best conveyed by listing
the chapters and their sections. 0. Fundamentals: Graphs. The
degree of a vertex. Paths and cycles. Connectivity. Trees and
forests. Bipartite graphs. Contraction and minors. Eulerian graphs.
Algebraic concepts. Related concepts. 1. Matchings: Matchings
in bipartite graphs. Matchings in general graphs. Coverings by
disjoint paths. 2. Connectivity: 2-connected graphs and subgraphs.
The structure of 3-connected graphs. The theorem of Menger. The
theorem of Mader. Edge-disjoint spanning trees. Linking paths
with given end vertices. 3. Graphs in the Plane: Topological prerequisites.
Plane graphs. Drawings. Planarity: Kuratowski's theorem. Algebraic
planarity criteria. Planarity and duality. 4. Colorings: Maps
and colors of plane graphs. Vertex colorings. Edge colorings.
List colorings. Perfect graphs. 5. Flows: Flows. Flows and circulations.
Networks. *k*-flows for small *k*. Flows and colorings.
Tutte's flow conjectures. 6. Substructures: Subgraphs. Topological
minors. Minors. The Hadwiger conjecture. The regularity lemma.
7. Ramsey Theory for Graphs: Ramsey's theorem. Ramsey numbers
of graphs. Ramsey induced. Ramsey theorems and connectivity. 8.
Hamiltonian Cycles: Simple sufficient conditions. Hamiltonian
cycles and degree sequence. Hamiltonian cycles in the square of
a graph. 9. Random Graphs: The concept of random graphs. The probabilistic
method. Properties of almost all graphs. Threshold functions and
second moments. 10. Minors. Trees, and the WQO: Well-quasi-ordering.
Trees: Kruskal's theorem. Tree decompositions. The theorem on
minors.

A few results are included without proofs but, for the most
part, clean, concise arguments are provided. The exercises, 250
in all, are collected at the end of each chapter. These are followed
by notes concomitant with the text, e.g., they include sources
for many of the proofs, further references, and historical remarks.
Problems are an essential part of any textbook and the selection
here is appropriate. Some exercises are graded for difficulty.
Some state results that follow directly from theorems but are
required to be proved ab initio.

Several distinguishing features contribute to the comfortable
`feel' of this book. For example, symbols and terms being defined
are listed in the margin: these margins also contain extensive
cross referencing. The index contains the English equivalents
for technical terms. In addition, the author includes a brief
English to German dictionary of technical terminology. In the
Foreword he gives a web site address to which readers may send
errors or misprints: it contained no entries at the time of this
writing.

R.C. Entringer

*Zentralblatt für Mathematik und ihre Grenzgebiete*

Rezensions-Überblick

Zurück zur Hauptseite