No label defined (Q4530616)

This book provides a gentle introduction to graph theory, focusing on the four-colour problem and related matters. Suitable as a textbook for advanced undergraduates or possibly beginning graduate students, it also provides a nice overview, and many details, of various approaches to the four-colour problem -- including the more recent successful ones (by Appel and Haken, with help from Koch, in 1976; by Robertson, Sanders, Seymour, and Thomas in 1997). Thus it has a place on the shelf of the professional graph theorist. The book is in three parts: I. Graphs, maps and the four-colour problem; II. Related topics (including the famous theorems of Kuratowski, Vizing, Brooks, and Heawood, and the conjectures of Hadwiger and Hajos); III. How to prove the four-colour theorem. Chapter titles are: 1. Introduction, 2. Basic graph theory, 3. Applications of Euler's formula, 4. Kempe's approach, 5. Other approaches, 6. Maps on surfaces with holes, 7. Kuratowski's theorem, 8. Colouring non-planar graphs; 9. Overview, 10. Reducibility, 11. Discharging. There are 70 exercises in all, a bibliography of 53 items, and an index. However, some of the page numbers given in the index misdirect (such as the entry for ``self-dual'') an the entries for ``surface'' do not lead to a definition of the concept. This is somewhat disappointing, as the book is intended to be self-contained. In Chapter 1, a map is implicitly taken to be on the plane, but not so in Chapter 6. The distinction could be made more clear. In Chapter 3 the applications of Euler's identity for the plane are mostly fairly immediate corollaries. Some of these are useful in Part III, but it would have been nice to see some additional deeper applications in Chapter 3, such as the classification of the Platonic solids (the lead-in given for the identity) or Pick's theorem. Theorem 6.13 is true for \(g= 1\) also (as Heawood showed), and Theorem 6.18 holds for \(n=1\) also. But these quibbles are either minor or subjective. Overall, the book has much to recommend it.