Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T02:33:57.027Z Has data issue: false hasContentIssue false

The complexity of the four colour theorem

Published online by Cambridge University Press:  01 August 2010

Cristian S. Calude
Affiliation:
Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand (email: c.calude@auckland.ac.nz)http://www.cs.auckland.ac.nz/∼cristian
Elena Calude
Affiliation:
Institute of Information and Mathematical Sciences, Massey University at Albany, Private Bag 102-904, North Shore MSC, New Zealandhttp://www.massey.ac.nz/∼ecalude

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The four colour theorem states that the vertices of every planar graph can be coloured with at most four colours so that no two adjacent vertices receive the same colour. This theorem is famous for many reasons, including the fact that its original 1977 proof includes a non-trivial computer verification. Recently, a formal proof of the theorem was obtained with the equational logic program Coq [G. Gonthier, ‘Formal proof–the four color theorem’, Notices of Amer. Math. Soc. 55 (2008) no. 11, 1382–1393]. In this paper we describe an implementation of the computational method introduced by C. S. Calude and co-workers [Evaluating the complexity of mathematical problems. Part 1’, Complex Systems 18 (2009) 267–285; A new measure of the difficulty of problems’, J. Mult. Valued Logic Soft Comput. 12 (2006) 285–307] to evaluate the complexity of the four colour theorem. Our method uses a Diophantine equational representation of the theorem. We show that the four colour theorem is in the complexity class ℭU,4. For comparison, the Riemann hypothesis is in class ℭU,3 while Fermat’s last theorem is in class ℭU,1.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2010