Издательство Oxford University Press, 2002, -147 pp.This book arose out of a third-year module in graph theory given at the University of Birmingham over the three years 1996-9, and again in 2001. This module was designed to be accessible to a large number of students (the prerequisites are minimal), but still to present some challenging material. The course centres around the famous 'four-colour conjecture', that every map can be coloured with four colours, subject to the usual convention that no two adjacent countries may be coloured the same. From its first appearance in mathematical folklore in the 1850s, until its eventual solution in the 1970s, this apparently simple problem has frustrated generations of mathematicians, both professional and amateur.
The book begins with a discussion of the early approaches of Kempe and Tait in the 1870s and 1880s, before revealing the flaws in their arguments, and then describing some of the ways in which the methods were refined, the problems axiomatised, and the conjectures generalized. In the course of this, we present several of the finest gems of the subject: Heawood's bound for map-colouring on a surface with holes, Kuratowski's theorem characterising which graphs (or maps) can be drawn on a surface without holes, and Vizing's theorem on the minimum number of colours needed to colour the edges of a graph. The final part of the book aims to provide some insight into the methods which eventually cracked the four-colour problem.
Much of the material in this book was covered in a single course of about 20 lectures, although some extra material has been added for completeness, and to facilitate a personal selection of topics. If students have met graphs before, then Chapter 2 can be largely omitted. If the aim is to study the four-colour theorem itself in some depth, then Chapters 7 and 8 are somewhat tangential and can also be omitted. On the other hand, a more general graph theory course can be made by picking a somewhat broader mix of topics from all the chapters.
Part I. Graphs, Maps and the Four-colour Problem.
Introduction.
Basic graph theory.
Applications of Euler's formula.
Kempe's approach.
Part II. Related Topics.
Other approaches to the four-colour problem.
Maps on surfaces with holes.
Kuratowski's theorem.
Colouring non-planar graphs.
Part III. How to Prove the Four-colour Theorem.
Overview.
Reductibility.
Discharging.
