Graphs, Colourings and the Four-colour Theorem
The theory of graph colouring has flourished over decades (in fact, already for one and a half centuries) with the planar map colouring problem having been its corner stone. Considered first as a riddle, the Four Colour Conjecture had soon turned into a nightmare for discrete mathematicians and graph theorists. But it was a nightmare with a very positive influence on the development of graph theory. Through numerous attempts and false proofs, it has motivated new notions, new theorems and new theories. And finally its solution, the proof that turned the Four Colour Conjecture into the Four Colour Theorem, is one of the strong concrete links between discrete mathematics and computer science. The proof depends heavily on computers, and no human being can check all details and cases, which is a blessing in the eyes of (most) computer scientists and rather a weird feature in the eyes of (some) mathematicians. The book under review presents a concise monograph on graph colouring results connected to the Four Colour Theorem. It describes ideas of early attempts, points out mistakes in published false proofs and gives a quite legible outline of ideas behind the computer-aided proofs. On the way to concluding sections, several classical results are presented, including the Euler formula for plane graphs, and theorems of Heawood, Brooks and Vizing. The last section contains a detailed and useful exposition of the discharging method. A certain drawback of the book is the lack of presentation of recent new results and directions in graph colouring - an area, which is very rich both in applications and theoretical results. Many classical results on colourings not directly related to the Four Colour Theorem are left out as well. Anybody seriously interested in graph colourings would thus need to look for other sources for further reading. On the other hand, the book provides a neatly wrapped up history of the Four Colour Conjecture; it is moreover published in the year of its 150th anniversary. As such it will please every reader. And last but not least, it is a thin book, which will not eat much space in your library; the contents to weight ratio is well above the average.