Editing Four color theorem (section)

===Higher surfaces===
One can also consider the coloring problem on surfaces other than the plane.{{sfnp|Ringel|1974}} The problem on the [[sphere]] or [[cylinder]] is equivalent to that on the plane. For closed (orientable or non-orientable) surfaces with positive [[genus (mathematics)|genus]], the maximum number ''p'' of colors needed depends on the surface's [[Euler characteristic]] χ according to the formula
: <math>p=\left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor,</math>
where the outermost brackets denote the [[floor function]].

Alternatively, for an [[orientable]] surface the formula can be given in terms of the genus of a surface, ''g'':
:: <math>p=\left\lfloor\frac{7 + \sqrt{1 + 48g }}{2}\right\rfloor.</math>

This formula, the [[Heawood conjecture]], was proposed by [[P. J. Heawood]] in 1890 and, after contributions by several people, proved by [[Gerhard Ringel]] and [[John William Theodore Youngs|J. W. T. Youngs]] in 1968. The only exception to the formula is the [[Klein bottle]], which has Euler characteristic 0 (hence the formula gives p = 7) but requires only 6 colors, as shown by [[Philip Franklin]] in 1934.

For example, the [[torus]] has Euler characteristic χ = 0 (and genus ''g'' = 1) and thus ''p'' = 7, so no more than 7 colors are required to color any map on a torus. This upper bound of 7 is [[Glossary of mathematical jargon#sharp|sharp]]: certain [[toroidal polyhedron|toroidal polyhedra]] such as the [[Szilassi polyhedron]] require seven colors.

A [[Möbius strip]] requires six colors {{harv|Tietze|1910}} as do [[1-planar graph]]s (graphs drawn with at most one simple crossing per edge) {{harv|Borodin|1984}}. If both the vertices and the faces of a planar graph are colored, in such a way that no two adjacent vertices, faces, or vertex-face pair have the same color, then again at most six colors are needed {{harv|Borodin|1984}}.

<gallery widths="200" heights="200">
7 colour torus.svg|A radially symmetric 7-colored torus &ndash; regions of the same colour wrap around along dotted lines
Tietze genus 2 colouring.svg|An 8-coloured double torus (genus-two surface) &ndash; bubbles denote unique combination of two regions
Taxel_genus_3_colouring.svg|A 9-coloured triple torus (genus-three surface) &ndash; blobs denote ends of their respective tunnels
Klein bottle colouring.svg|A 6-colored [[Klein bottle]]
Tietze Moebius.svg|[[Heinrich Tietze|Tietze's]] subdivision of a [[Möbius strip]] into six mutually adjacent regions, requiring six colors. The vertices and edges of the subdivision form an embedding of [[Tietze's graph]] onto the strip.
Szilassi polyhedron 3D model.svg|Interactive [[Szilassi polyhedron]] model with each of 7 faces adjacent to every other &ndash; in [[Media:Szilassi polyhedron 3D model.svg|the SVG image]], move the mouse to rotate it
</gallery>

For graphs whose vertices are represented as pairs of points on two distinct surfaces, with edges drawn as non-crossing curves on one of the two surfaces, the chromatic number can be at least 9 and is at most 12, but more precise bounds are not known; this is [[Gerhard Ringel]]'s [[Earth–Moon problem]].<ref>{{citation
 | last = Gethner | first = Ellen | author-link = Ellen Gethner
 | editor1-last = Gera | editor1-first = Ralucca | editor1-link = Ralucca Gera
 | editor2-last = Haynes | editor2-first = Teresa W. | editor2-link = Teresa W. Haynes
 | editor3-last = Hedetniemi | editor3-first = Stephen T.
 | contribution = To the Moon and beyond
 | doi = 10.1007/978-3-319-97686-0_11
 | mr = 3930641
 | pages = 115–133
 | publisher = Springer International Publishing
 | series = Problem Books in Mathematics
 | title = Graph Theory: Favorite Conjectures and Open Problems, II
 | year = 2018| isbn = 978-3-319-97684-6 }}</ref>