Acyclic colourings of planar graphs

M.Sc.Within the field of Graph Theory the many ways in which graphs can be coloured have received a lot of attention over the years. T.R. Jensen and B. Toft provided a summary in [8] of the most important results and research done in this field. These results were cited by R. Diestel in [5] as “The Four Colour Problem” wherein it is attempted to colour every map with four colours in such a way that adjacent countries will be assigned different colours. This was first noted as a problem by Francis Guthrie in 1852 and later, in 1878, by Cayley who presented it to the London Mathematical Society. In 1879 Kempe published a proof, but it was incorrect and lead to the adjustment by Heawood in 1890 to prove the five colour theorem. In 1977 Appel and Haken were the first to publish a solution for the four colour problem in [2] of which the proof was mostly based on work done by Birkhoff and Heesch. The proof is done in two steps that can be described as follows: firstly it is shown that every triangulation contains at least one of 1482 certain “unavoidable configurations” and secondly, by using a computer, it is shown that each of these configurations is “reducible”. In this context the term “reducible” is used in the sense that any plane triangulation containing such a configuration is 4-colourable by piecing together 4- colourings of smaller plane triangulations. These two steps resulted in an inductive proof that all plane triangulations and therefore all planar graphs are 4-colourable