scientific article; zbMATH DE number 1748997
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.
- Diameter of 4-colourable graphs
- 3-maps
- Coloring graphs with no \(\text{odd-}K_4\)
- Combinatorial RNA design: designability and structure-approximating algorithm in Watson-Crick and Nussinov-Jacobson energy models
- Some properties of non-bicolorable hypergraphs and the four-color problem
- Graph coloring and semidefinite rank
- Torsion cohomology for solvable groups of finite rank.
- An approximate algorithm for the chromatic number of graphs
- Facial non-repetitive edge-coloring of plane graphs
- scientific article; zbMATH DE number 3843768 (Why is no real title available?)
- Explorations in topology. Map coloring, surfaces and knots
- scientific article; zbMATH DE number 3912383 (Why is no real title available?)
- scientific article; zbMATH DE number 3916298 (Why is no real title available?)
- scientific article; zbMATH DE number 107606 (Why is no real title available?)
- Total embedding distributions of Ringel ladders
- Triangulations of the sphere, bitrades and abelian groups
- Metrically homogeneous graphs of diameter \(3\)
- Combinatorial stacks and the four-color theorem
- Graph coloring and semidefinite rank
- On non-traceable 3-connected planar cubic graphs of minimum order
- Minimal covering unrestricted location of obnoxious facilities: bi-objective formulation and a case study
- On Barnette's conjecture
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4530616)
