On the Colouring of Maps
Colouring is one of the earliest enjoyable activities that we engage in as children, and for many of us this continues into our adult lives. So it is not surprising that mathematicians of all kinds – amateur and professional, young and old alike – have been fascinated by questions concerning the colouring of a flat surface, or the plane as we refer to it. Mathematically every individual point on the plane can be allocated a colour, although this may be a difficult concept to visualise, since a single point has no length or breadth, only position. It may help to think of colour as a label attached to a point rather than something that we can actually see.
In practice, of course, our initial experience of colouring is the application of crayon or paint to sheets of paper. In this case the colouring is always in blobs or patches which have length and breadth, however small. Mathematicians refer to such colouring of the plane as map-type colouring. More precisely, map-type colouring of the plane is the subdivision of the entire plane into non-overlapping regions bounded by simple closed curves, and the assignment of the same colour to all points in the same region. Whether we just daub paint onto a blank sheet of paper, or meticulously colour in pre-drawn shapes using pencil or crayon, what we end up with is essentially a map comprising different coloured regions, as illustrated here.
Questions concerning the colouring of maps have fascinated people for hundreds of years, and no doubt longer. Back in the mid nineteenth century Francis Guthrie suggested that it is possible to colour any map with just four colours, whilst still ensuring that adjacent regions with a common boundary have different colours. (For this purpose a boundary is considered to be not just a single point, but a line of non-zero length separating two adjacent regions.) Here is a possible four-colouring of the above illustration..
Guthrie’s proposal became known as the Four Colour Conjecture, but it remained just that – a likely but unproven conjecture – until 1976 when Appel and Haken proved it to be correct. Their proof was not without controversy, because it relied on computer software, which meant that the logical arguments could not be analysed and verified by other researchers in the normal way. However, subsequent independent research has confirmed the result (see Wikipedia entry).
The Four Colour Theorem relates closely to one of the currently unsolved problems in Mathematics, that of the Chromatic Number of the Plane, Cp. This is the minimum number of colours required to colour the plane so that no two points unit distance apart are the same colour. Although still an unsolved problem it is known that Cp is 5, 6 or 7. The possibility that it might be as low as 4 was only excluded in 2018, again using computer software assistance (see Hadwiger-Nelson problem in Wikipedia). An associated more constrained, but similarly unsolved, problem is the Chromatic Number of the Plane under Map-Type Colouring, defined as follows.
The Chromatic Number of the Plane under Map-Type Colouring, Cpm, is the minimum number of colours required to colour the plane under map-type colouring, so that no two points unit distance apart are the same colour.
A moment’s thought will reveal that every region in such a colouring must be of small enough size to fit inside a circle of diameter one unit. And any two different regions of the same colour must either both fit inside a circle of unit diameter or the distance between their closest boundaries must be greater than one unit.
To express the problem in everyday terms, can you completely colour a blank sheet of A4 paper using seven colours ensuring that no two points with the same colour are exactly one inch apart? And if you succeed with seven colours, can you do it with only six? And what about 5? Until the 1970s the best that could be said was that the smallest number of colours must be 5, 6, or 7. The fact that you can use seven colours can be easily demonstrated, as in the following example.
Here the entire plane is covered with interlocking hexagons, with repeated regular colouring as shown, ensuring that any two points one inch apart have different colours.
Another way to colour a planar map with seven colours is to tile the plane with squares and colour them systematically, as shown below.
The squares are arranged in rows, and every row has exactly the same repeated ordering of colours. The rows need to be positioned horizontally quite carefully. Assume the squares have length and breadth 0.7 inches (this ensures their diagonals are slightly under one inch). In each (and every) row select a red square (for example). Adjust the horizontal position of the row to ensure that the bottom-left corner of the selected square is 1.04 inches to the right of the top-right corner of a red square in the row beneath (1.04 inches is slightly under 1.5 times the breadth of a square). This will then ensure that the bottom right corner of the nearest red square two rows above the selected square is 1.004 inches from its top-left corner. Once again any two points in the map distance one inch apart will have different colours.
In the late 1970s, whilst lecturing in Mathematics at the University of Aberdeen, I started exploring possible improvements on the range of values for Cpm, more specifically whether a value of 5 could be excluded. I was delighted after much study to be able to prove that every 5-coloured planar map must inevitably contain a pair of points of the same colour unit distance apart, and that consequently Cpm must be either 6 or 7.
Imagine my consternation, then, when on preparing the work for publication I discovered that the result had already been published a few years previously by a highly regarded mathematician at the University of Nottingham, Douglas Woodall[1]. On reading Woodall’s paper I also became extremely puzzled. I knew from my own analysis that certain aspects of the proof were difficult, and yet Woodall seemed to have produced a proof that circumnavigated one of the most difficult parts. So with an attitude of “How did he manage this?” I went through his proof rigorously, and consequently spotted a flaw. The proof depended on an assertion that was incorrect, which could be demonstrated using a counter-example.
As I later communicated to Professor Alexander Soifer, University of Colorado, before I started researching this topic I was totally unaware of Woodall’s proof, which was both my folly and my good fortune. Folly, in that I should have conducted a more exhaustive literature search before devoting my time to the problem. Good fortune in that had I been aware of Woodall’s paper I would not have spent any time on the problem at all; I certainly would not have had the temerity to check Woodall’s proof for accuracy. In his well-known work The Mathematical Coloring Book[2] Professor Soifer makes the point that no criticism should be directed at Douglas Woodall, since his work was valuable and mistakes of this kind are always possible. I agree with him, particularly since in this case the flaw was not immediately obvious, as was demonstrated by the fact that none of the referees of Woodall’s paper spotted the problem!
So I had to revise the content of my research paper to include a reference to Woodall’s earlier work, showing where his proof failed, and then present my own findings (see 1979 paper). However, when I sent the result to the editor of the Journal of Combinatorial Theory Series A (JCTA) I received a courteous reply that the paper was not considered sufficiently important to merit publication, and inviting me to write a short note to confirm that Woodall’s result was indeed correct, even though the proof in his paper was flawed.
This, of course, I did[3] (see 1981 note) and there the matter rested for many years. Indeed I gave it very little further thought, since from then on my time was fully occupied, first of all in taking up a very fulfilling position lecturing in Mathematics at the University of Botswana and Swaziland, and then on my return to Aberdeen switching my subject area from Mathematics to the rapidly-expanding discipline of Computing Science.
Nevertheless not all mathematicians agreed with the decision of the JCTA editor. In 2003 Alexander Soifer, Professor of Mathematics at the University of Colorado, contacted me to express his disappointment with what had happened, and to propose that my proof should be published in the journal Geombinatorics Quarterly. So it was that in April 2005 a featured essay “On Stephen P. Townsend’s 1979 Proof” by Professor Soifer appeared[4], introducing my paper[5] entitled “Colouring the Plane with no Monochrome Units.” (See featured essay and 2005 paper.)
Later on, in 2009, Professor Soifer published The Mathematical
Coloring Book
[2],
his distinguished work on “The Mathematics of Coloring and the Colorful Life of its Creators.”
He was most generous in devoting a chapter to what is now called the Townsend-Woodall
5-Color Theorem: Every 5-colored planar map contains two points of the same
color unit distance apart. Professor Soifer invited me to expand on my original
work, particularly to make the proof more accessible to the general reader.
This I attempted to do, but must leave it to the reader to assess whether or
not this was successful (see
chapter 24 of The Mathematical Coloring Book). A second
edition of this book, entitled The New Mathematical Coloring Book, is
due to be published in April 2024[6].
So there the matter rests for the present. The chromatic number of the plane under map-type colouring is either 6 or 7, but we don’t currently know which. To prove one or the other someone has to do one of the following. Either prove that every 6-coloured planar map contains two points unit distance apart with the same colour, in which case the chromatic number is 7. Alternatively show that there is a way to use just six colours to colour the plane using map-type colouring whilst ensuring that no two points unit distance apart have the same colour, in which case the chromatic number is 6.
All the best if you are sufficiently intrigued to try to solve this puzzle yourself!
Steve Townsend,
February 2024