Reinhard Diestel


Besprechung aus: Zentralblatt

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

Zurück zur Hauptseite