Editing Four color theorem (section)

==Generalizations==
===Infinite graphs===
[[File:Torus with seven colours.svg|thumb|300px|By joining the single arrows together and the double arrows together, one obtains a [[torus]] with seven mutually touching regions; therefore seven colors are necessary.]]
[[File:Projection color torus.png|480px|thumb|This construction shows the torus divided into the maximum of seven regions, each one of which touches every other.]]
The four color theorem applies not only to finite planar graphs, but also to [[infinite graph]]s that can be drawn without crossings in the plane, and even more generally to infinite graphs (possibly with an uncountable number of vertices) for which every finite subgraph is planar. To prove this, one can combine a proof of the theorem for finite planar graphs with the [[De Bruijn–Erdős theorem (graph theory)|De Bruijn–Erdős theorem]] stating that, if every finite subgraph of an infinite graph is ''k''-colorable, then the whole graph is also ''k''-colorable {{harvtxt|Nash-Williams|1967}}. This can also be seen as an immediate consequence of [[Kurt Gödel]]'s [[compactness theorem]] for [[first-order logic]], simply by expressing the colorability of an infinite graph with a set of logical formulae.

===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>

===Solid regions===
[[File:Visual proof mutually touching solids.svg|thumb|Proof without words that the number of colours needed is unbounded in three or more dimensions]]
There is no obvious extension of the coloring result to three-dimensional solid regions. By using a set of ''n'' flexible rods, one can arrange that every rod touches every other rod. The set would then require ''n'' colors, or ''n''+1 including the empty space that also touches every rod. The number ''n'' can be taken to be any integer, as large as desired. Such examples were known to Fredrick Guthrie in 1880.{{sfnp|Wilson|2014|p=15}} Even for axis-parallel [[cuboid]]s (considered to be adjacent when two cuboids share a two-dimensional boundary area), an unbounded number of colors may be necessary.<ref>{{harvnb|Reed|Allwright|2008}}; {{harvtxt|Magnant|Martin|2011}}</ref>
{{clear|left}}