Professional paper

Graph Colouring and its Application within Cartography

Mate Glaurdić ; Faculty of Geodesy, University of Zagreb, Zagreb, Croatia
Jelena Beban-Brkić ; Faculty of Geodesy, University of Zagreb, Zagreb, Croatia
Dražen Tutić orcid.org/0000-0001-9336-2892 ; Faculty of Geodesy, University of Zagreb, Zagreb, Croatia

Abstract

The problem of colouring geographical political maps has historically been associated with the theory of graph colouring. In the middle of the 19th century the following question was posed: how many colours are needed to colour a map in a way that countries sharing a border are coloured differently. The solution has been reached by linking maps and graphs. It took more than a century to prove that 4 colours are sufficient to create a map in which neighbouring countries have different colours.

Keywords

graph; graph colouring; map; map colouring; the four colour theorem

Hrčak ID:

174107

URI

https://hrcak.srce.hr/174107

Publication date:

16.1.2017.

Article data in other languages: croatian

Visits: 2.085 *