Reinhard Diestel

Graph Theory

Review from Acta Scientiarum Mathematicarum

Graph theory is gaining fast growing importance in college and university education. Its applications in computer science, economics, optimization make graph theory an obligatory part in syllabuses of electrical engineering, operations research, economics majors. Following this trend the number of graph theory textbooks on the market is also fast growing. Reinhard Diestel's work is certainly much more than just a small supplement to the previous works. It is an outstanding attempt to give a firm basis for graph theoretical studies and to give a glimpse of the most current techniques. In order to do that the author covers topics that are not traditional in earlier textbooks or not even covered in any of them.

The book consists of twelve chapters: The basics, Matching, Connectivity, Planar graphs, Colouring, Flows, Substructures in sparse graphs, Ramsey theory for graphs, Hamiltonian cycles, Random graphs, Minors, trees, and WQO.

We should point out that some chapters are completely new in the literature. For example, Szemerédi's regularity lemma and Seymour-Robertson theory are not carefully thought about so far in textbooks. Some classical topics also give pleasant surprises for the reader. In addition to the five color theorem, Thomassen's extremely simple proof that each simple planar graph is 5-choosable is also presented.

The presentation is very condensed. This is achieved by careful thinking to choose the right proof to present. This is a result of great teaching experience and extensive discussion with fellow researchers over several years. An earlier German version preceded the book.

The presentation of the book is attractive. Notation and cross references (between different chapters) are listed in the margin. At first look this gives a strange appearance for the book but the careful readers (especially the novice readers) obtain considerable extra information by following the cross references. Each chapter ends with notes, containing very helpful historical notes and references. At the end of the book an Index and a Symbol index help the reader to find the necessary pointers. There is no complete list of references in the book (the references of the book are given at the end of chapters, as mentioned earlier).

Each chapter is supplemented with exercises. The hardness of the exercises is marked by - and + signs. No solutions are given although when the author felt it necessary an immediate hint follows the exercise.

Some of the chapters of the book can be used in undergraduate courses. But the major use of the book will be at graduate courses and graph theory seminars. We highly recommend this book for graph theorists, graduate students in graph theory, and anyone who needs graph theoretical methods in his/her work. This book cannot be substituted with any other book on the present textbook market. The referee's opinion is that the present book has the chance to become the standard textbook for graph theory.

Peter Hajnal (Szeged)
Acta Scientiarum Mathematicarum

List of reviews
Return to home page