{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T15:55:43Z","timestamp":1774540543891,"version":"3.50.1"},"reference-count":12,"publisher":"Wiley","license":[{"start":{"date-parts":[[2010,8,1]],"date-time":"2010-08-01T00:00:00Z","timestamp":1280620800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.\u00a0Gonthier, \u2018Formal proof\u2013the four color theorem\u2019, <jats:italic>Notices of Amer. Math. Soc.<\/jats:italic> 55 (2008) no.\u00a011, 1382\u20131393]. In this paper we describe an implementation of the computational method introduced by C.\u00a0S. Calude and co-workers [Evaluating the complexity of mathematical problems. Part\u00a01\u2019, <jats:italic>Complex Systems<\/jats:italic> 18 (2009) 267\u2013285; A new measure of the difficulty of problems\u2019, <jats:italic>J.\u00a0Mult. Valued Logic Soft Comput.<\/jats:italic> 12 (2006) 285\u2013307] 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 \u212d<jats:sub><jats:italic>U<\/jats:italic>,4<\/jats:sub>. For comparison, the Riemann hypothesis is in class \u212d<jats:sub><jats:italic>U<\/jats:italic>,3<\/jats:sub> while Fermat\u2019s last theorem is in class\u00a0\u212d<jats:sub><jats:italic>U<\/jats:italic>,1<\/jats:sub>.<\/jats:p>","DOI":"10.1112\/s1461157009000461","type":"journal-article","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T11:09:45Z","timestamp":1282907385000},"page":"414-425","source":"Crossref","is-referenced-by-count":7,"title":["The complexity of the four colour theorem"],"prefix":"10.1112","volume":"13","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[]},{"given":"Elena","family":"Calude","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2010,8,1]]},"reference":[{"key":"S1461157009000461_ref8","first-page":"167","volume":"84","author":"Calude","year":"2004","journal-title":"Bull. EATCS"},{"key":"S1461157009000461_ref7","first-page":"285","volume":"12","author":"Calude","year":"2006","journal-title":"J. Mult. Valued Logic Soft Comput."},{"key":"S1461157009000461_ref6","doi-asserted-by":"crossref","first-page":"387","DOI":"10.25088\/ComplexSystems.18.4.387","volume":"18","author":"Calude","year":"2010","journal-title":"Complex Systems"},{"key":"S1461157009000461_ref5","doi-asserted-by":"crossref","first-page":"267","DOI":"10.25088\/ComplexSystems.18.3.267","volume":"18","author":"Calude","year":"2009","journal-title":"Complex Systems"},{"key":"S1461157009000461_ref17","volume-title":"Four colours suffice","author":"Wilson","year":"2002"},{"key":"S1461157009000461_ref10","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1080\/10586458.2002.10504481","volume":"11","author":"Calude","year":"2002","journal-title":"Experiment. Math."},{"key":"S1461157009000461_ref3","first-page":"27","volume":"38","author":"Calude","year":"2001","journal-title":"NZ Math. Magazine"},{"key":"S1461157009000461_ref2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1215\/ijm\/1256049011","volume":"21","author":"Appel","year":"1977","journal-title":"Illinois J. Math."},{"key":"S1461157009000461_ref14","first-page":"1382","volume":"55","author":"Gonthier","year":"2008","journal-title":"Notices Amer. Math. Soc."},{"key":"S1461157009000461_ref1","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1215\/ijm\/1256049012","volume":"21","author":"Appel","year":"1977","journal-title":"Illinois J. Math."},{"key":"S1461157009000461_ref13","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1090\/pspum\/028.2\/0432534","volume-title":"Mathematical developments arising from Hilbert problems","author":"Davis","year":"1976"},{"key":"S1461157009000461_ref4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04978-5","volume-title":"Information and randomness: an algorithmic perspective","author":"Calude","year":"2002"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157009000461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T13:14:59Z","timestamp":1732108499000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157009000461\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,1]]},"references-count":12,"alternative-id":["S1461157009000461"],"URL":"https:\/\/doi.org\/10.1112\/s1461157009000461","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,1]]}}}