Graph theory. (English) Zbl 1134.05001

Graduate Texts in Mathematics 244. Berlin: Springer (ISBN 978-1-84628-969-9/hbk). xii, 651 p. (2008).
This textbook started out as an attempt to update the authors’ previous book [J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing, New York (1976)]. However the project rapidly expanded into a much more substantial rewrite, much larger than the original.
The topics covered include: basic material on graphs and digraphs, basic material on cycles and trees: tree-search algorithms: network flows (max-flow min cut, Menger etc.): algorithm complexity: more connectivity results for graphs: planar graphs and the four-colour problem: Turán’s theorem, Ramsey’s theorem and the regularity lemma: probabilistic methods: vertex colourings and colourings of maps: matchings, edge-colourings and Hamilton cycles, covering and packings in directed graphs, electrical flows and networks, and integer flows and coverings. Digraphs, algorithmic aspects (including complexity) and some applications are discussed in more detail than in some comparable graph theory texts: the theory of graph minors, which the authors felt they could not do justice too in a book of this length, is only touched upon, and algebraic graph theory, and automorphism groups, are perhaps developed in their own right rather less than in some comparable texts.
Most results mentioned are proved. The authors explain that they have written a text which is designed to be usable both for a basic graph theory course, based on the introductory sections of a few chapters (some particular suggestions in this direction are made in the blog, see below) but also to be usable as an introduction to research in graph theory, by including more advanced topics in each chapter. There are a large number of exercises in the book, of varying degrees of difficulty. The text contains drawings of many standard interesting graphs, which are listed at the end. The authors have attempted to bring out various commonly used proof techniques (e.g. double counting, Möbius inversion, Lovász local lemma, etc.) at various points, either as insets or subsections. There is a list of unsolved problems at the end, and an extensive and up-to-date bibliography.
A webpage for the book http://blogs.springer.com/bondyandmurty/ has a few minor errors (e.g. in the proof of Theorem 3.1) noted on it, and contains hints for some exercises, some suggested courses for different classes of users of the books (mathematics students, computer science students, operational research students, graduate courses), and some links to relevant webpages.


05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05Cxx Graph theory