Acyclic colourings of planar graphs

DSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Prof. I. Broere en_US
dc.contributor.author Raubenheimer, Fredrika Susanna
dc.date.accessioned 2012-08-20T10:11:43Z
dc.date.available 2012-08-20T10:11:43Z
dc.date.issued 2012-08-20
dc.date.submitted 2012-05-23
dc.identifier.uri http://hdl.handle.net/10210/6259
dc.description M.Sc. en_US
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.subject Graph coloring en_US
dc.subject Four-color problem
dc.subject Cayley graphs
dc.title Acyclic colourings of planar graphs en_US
dc.type Thesis en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UJDigispace


Advanced Search

Browse

My Account