Earth–Moon problem

Last updated May 01, 2024

The Earth–Moon problem is an unsolved problem on graph coloring in mathematics. It is an extension of the planar map coloring problem (solved by the four color theorem), and was posed by Gerhard Ringel in 1959.^[1] An intuitive form of the problem asks how many colors are needed to color political maps of the Earth and Moon, in a hypothetical future where each Earth country has a Moon colony which must be given the same color. In mathematical terms, it seeks the chromatic number of biplanar graphs. It is known that this number is at least 9 and at most 12.

The Earth–Moon problem has been extended to analogous problems of coloring maps on any number of planets. For this extension the lower bounds and upper bounds on the number of colors are closer, within two of each other. One real-world application of the Earth–Moon problem involves testing printed circuit boards.

Formulation and history

In the map coloring problem, finitely many simply connected regions in the Euclidean plane or a topologically equivalent space, such as countries on the surface of the Earth, are to be colored so that, when two regions share a boundary of nonzero length, they have different colors. It can be transformed into a graph coloring problem by making a vertex for each region and an edge for each two neighboring regions, producing a planar graph whose vertices are to be colored. Corresponding to the requirement that adjacent regions should have different colors, adjacent vertices (the two endpoints of any edge) should have different colors. According to the four color theorem, the resulting planar graph (or any planar graph) can be colored using at most four different colors, no matter how many regions are given.^[2]

In 1959, Gerhard Ringel published a book on colorings of surfaces, surveying the results at the time on the four color problem and the Heawood conjecture on coloring maps on non-planar surfaces such as the torus and Klein bottle.^[1] Both had been long-conjectured but were unsolved at the time. Ringel himself later proved the Heawood conjecture in a 1968 paper with J. W. T. Youngs;^[2]^[3] the four-color theorem evaded proof until 1976.^[2]^[4] Another topic of Ringel's book was a result of Percy John Heawood from 1890, on the "empire problem": coloring maps in which each empire has some number $m$ of distinct regions on the Earth (a home country and $m-1$ colonies). As Heawood showed for $m=2$ , and Ringel later proved with Jackson in 1984 for $m>2$ , $6m$ colors are necessary and sufficient.^[2]^[5]^[6]^[7] Perhaps inspired by this problem and the dawn of the space age, Ringel included the Earth-Moon problem in his book as a variant of the empire problem in which the colonies are on the Moon rather than on the Earth.^[1]^[2] In a formulation of Martin Gardner, the colonies are instead on Mars.^[6]

In Ringel's Earth–Moon problem, each country on the Earth has a corresponding colony on the surface of the Moon, that must be given the same color. These colonies may have borders that are completely different from the arrangement of the borders on the Earth. The countries must be colored, using the same color for each country and its colony, so that when two countries share a border either on the Earth or on the Moon they are given different colors. Ringel's problem asks: how many colors are needed to guarantee that the countries can all be colored, no matter how their boundaries are arranged?^[2] Ringel proved that the number of colors needed was at least 8 and at most 12, conjecturing that 8 was the correct answer.^[6]

Again, one can phrase the same question equivalently as one in graph theory, with a single vertex for each pair of a country and its colony, and an edge for each adjacency between countries or colonies. As in the planar case, after this transformation, it is the vertices that must be colored, with different colors for the endpoints of each edge. The graphs that result in this version of the problem are biplanar graphs, or equivalently the graphs of thickness two: their edges can be partitioned into two subsets (the edges coming from Earth adjacencies and those coming from Moon adjacencies) such that the corresponding two subgraphs are both planar. In mathematical terms, Ringel's problem asks for the maximum chromatic number of biplanar graphs.^[2]

Bounds

A biplanar graph on $n$ vertices has at most $6n-12$ edges (double the number that a planar graph can have), from which it follows from the degree sum formula that it has at least one vertex with at most 11 neighbors. Removing this vertex, coloring the remaining graph recursively, and then using the smallest-numbered unused color for the removed vertex leads to a coloring with at most 12 colors; this is the greedy coloring for a degeneracy ordering of the graph. Therefore, biplanar graphs require at most 12 colors.^[2]

An example of a biplanar graph requiring 9 colors can be constructed as the join of a 6-vertex complete graph and a 5-vertex cycle graph. This means that these two subgraphs are connected by all possible edges from one subgraph to the other. The resulting graph has 11 vertices, and requires 6 colors for the complete subgraph and 3 colors for the cycle subgraph, giving 9 colors overall.^[2] This construction, by Thom Sulanke in 1974, disproved the conjecture of Ringel that 8 colors would always suffice.^[6] Subsequently, an infinite family of biplanar 9-critical graphs (minimal graphs that require nine colors) has been constructed.^[8]^[9]

Despite a lack of further progress on the problem, in 2018 Ellen Gethner conjectured that the correct number of colors for this problem is 11. She suggests several candidates for 10-chromatic biplanar graphs, including the graph $C_{7}\boxtimes K_{4}$ obtained as the strong product of a cycle graph with a clique, and the graph obtained by removing any vertex from $C_{5}\boxtimes K_{4}$ . These graphs can be shown to require 10 colors, because they have no independent set large enough to be the largest color class in a coloring with fewer colors. Additionally, they meet the bounds on the number of edges a biplanar graph can have. However, a representation of them as biplanar graphs (or Earth–Moon maps) remains elusive.^[10]

Application

One application of colorings of biplanar graphs involves testing printed circuit boards for short circuits. The electrical conductors within these boards include crossings, but (for double-sided printed circuit boards) their adjacencies can be assumed to form a biplanar graph. After coloring this graph, short circuits between adjacent conductors can be detected by adding extra circuitry to connect all conductors with the same colors to each other and testing for connections between pairs of different colors. With some care, this idea can be used to reduce the number of tests needed per circuit to only four.^[2]^[11]

Generalizations

Various generalizations of the problem have also been considered, including versions of the problem with more than two planets or with countries that can have more than one region per planet.^[12]^[13] Maps with one planet and multiple regions per country give Heawood's empire problem.^[2]^[7] Maps with more than two planets but only one region per planet correspond to graphs whose thickness is at most equal to the number of planets. For these graphs, more precise (although still incomplete) results are known. For the graphs of thickness $t\geq 3$ , and the corresponding $t$ -planet maps, the chromatic number is at most $6t$ by the same degeneracy argument used in the Earth–Moon problem. As well, for $t\geq 3$ , a complete graph with $6t-2$ vertices has thickness $t$ , showing some of these graphs require $6t-2$ colors. Thus, in this case, the upper and lower bounds are within two colors of each other.^[14]

Related Research Articles

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary of non-zero length. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubts remain.

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

In graph theory, a uniquely colorable graph is a $k$ -chromatic graph that has only one possible (proper) $k$ -coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into $k$ independent sets and there is no way to partition them into $k - 1$ independent sets.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS: A000934, the chromatic number or Heawood number.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

In mathematics, the Heawood number of a surface is an upper bound for the number of colors that suffice to color any graph embedded in the surface.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.$

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph.

In graph theory, the thickness of a graph $G$ is the minimum number of planar graphs into which the edges of $G$ can be partitioned. That is, if there exists a collection of $k$ planar graphs, all having the same set of vertices, such that the union of these planar graphs is $G$ , then the thickness of $G$ is at most $k$ . In other words, the thickness of a graph is the minimum number of planar subgraphs whose union equals to graph $G$ .

References

1 2 3 Ringel, Gerhard (1959), Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, Berlin: VEB Deutscher Verlag der Wissenschaften, MR 0109349
1 2 3 4 5 6 7 8 9 10 11 Hutchinson, Joan P. (October 1993), "Coloring ordinary maps, maps of empires, and maps of the Moon", Mathematics Magazine , 66 (4): 211–226, doi:10.2307/2690733, JSTOR 2690733
↑ Ringel, G.; Youngs, J. W. T. (1968), "Solution of the Heawood Map-Coloring Problem", Proc. Natl. Acad. Sci. USA, vol. 60, no. 2, pp. 438–445, Bibcode:1968PNAS...60..438R, doi: 10.1073/pnas.60.2.438 , PMC 225066 , PMID 16591648
↑ Appel, K.; Haken, W. (1976), "Every planar map is four colorable", Bulletin of the American Mathematical Society, 82 (5): 711–712, doi:10.1090/S0002-9904-1976-14122-5, MR 0424602
↑ Heawood, P. J. (1890), "Map-Colour Theorem", Quarterly Journal of Mathematics, Oxford, vol. 24, pp. 332–338
1 2 3 4 Gardner, Martin (February 1980), "The coloring of unusual maps leads into uncharted territory", Mathematical Games, Scientific American , 242 (2): 14–23, doi:10.1038/scientificamerican0280-14, JSTOR 24966248
1 2 Jackson, Brad; Ringel, Gerhard (1984), "Solution of Heawood's empire problem in the plane", Journal für die Reine und Angewandte Mathematik, 347: 146–153, doi:10.1515/crll.1984.347.146, MR 0733049
↑ Boutin, Debra L.; Gethner, Ellen; Sulanke, Thom (2008), "Thickness-two graphs, I: New nine-critical graphs, permuted layer graphs, and Catlin's graphs", Journal of Graph Theory , 57 (3): 198–214, doi:10.1002/jgt.20282, MR 2384020, S2CID 39576387
↑ Gethner, Ellen; Sulanke, Thom (2009), "Thickness-two graphs, II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs", Graphs and Combinatorics , 25 (2): 197–217, doi:10.1007/s00373-008-0833-5, MR 2511878, S2CID 2209541
↑ Gethner, Ellen (2018), "To the Moon and beyond", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi:10.1007/978-3-319-97686-0_11, MR 3930641
↑ Garey, M.; Johnson, D.; So, Hing (October 1976), "An application of graph coloring to printed circuit testing", IEEE Transactions on Circuits and Systems, 23 (10): 591–599, doi:10.1109/tcs.1976.1084138
↑ Stewart, Ian (April 1993), "The rise and fall of the Lunar M-pire", Mathematical Recreations, Scientific American , 268 (4): 120–121, Bibcode:1993SciAm.268d.120S, doi:10.1038/scientificamerican0493-120, JSTOR 24941454
↑ Jackson, Brad; Ringel, Gerhard (2000), "Variations on Ringel's earth-moon problem", Discrete Mathematics , 211 (1–3): 233–242, doi:10.1016/S0012-365X(99)00278-2, MR 1735339
↑ Alekseev, V. B.; Gončakov, V. S. (1976), "The thickness of an arbitrary complete graph", Matematicheskii Sbornik , New Series, 101 (143): 212–230, Bibcode:1976SbMat..30..187A, doi:10.1070/SM1976v030n02ABEH002267, MR 0460162

External links

Weisstein, Eric W., "Earth-Moon Problem", MathWorld
"Earth-Moon Problem", Open Problem Garden

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[ringel-1] 1 2 3 Ringel, Gerhard (1959), Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, Berlin: VEB Deutscher Verlag der Wissenschaften, MR 0109349

[hutchinson-2] 1 2 3 4 5 6 7 8 9 10 11 Hutchinson, Joan P. (October 1993), "Coloring ordinary maps, maps of empires, and maps of the Moon", Mathematics Magazine , 66 (4): 211–226, doi:10.2307/2690733, JSTOR 2690733

[ringel-youngs-3] Ringel, G.; Youngs, J. W. T. (1968), "Solution of the Heawood Map-Coloring Problem", Proc. Natl. Acad. Sci. USA, vol. 60, no. 2, pp. 438–445, Bibcode:1968PNAS...60..438R, doi: 10.1073/pnas.60.2.438 , PMC 225066 , PMID 16591648

[appel-haken-4] Appel, K.; Haken, W. (1976), "Every planar map is four colorable", Bulletin of the American Mathematical Society, 82 (5): 711–712, doi:10.1090/S0002-9904-1976-14122-5, MR 0424602

[heawood-5] Heawood, P. J. (1890), "Map-Colour Theorem", Quarterly Journal of Mathematics, Oxford, vol. 24, pp. 332–338

[gardner-6] 1 2 3 4 Gardner, Martin (February 1980), "The coloring of unusual maps leads into uncharted territory", Mathematical Games, Scientific American , 242 (2): 14–23, doi:10.1038/scientificamerican0280-14, JSTOR 24966248

[jr-empire-7] 1 2 Jackson, Brad; Ringel, Gerhard (1984), "Solution of Heawood's empire problem in the plane", Journal für die Reine und Angewandte Mathematik, 347: 146–153, doi:10.1515/crll.1984.347.146, MR 0733049

[boutin-gethner-sulanke-8] Boutin, Debra L.; Gethner, Ellen; Sulanke, Thom (2008), "Thickness-two graphs, I: New nine-critical graphs, permuted layer graphs, and Catlin's graphs", Journal of Graph Theory , 57 (3): 198–214, doi:10.1002/jgt.20282, MR 2384020, S2CID 39576387

[gethner-sulanke-9] Gethner, Ellen; Sulanke, Thom (2009), "Thickness-two graphs, II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs", Graphs and Combinatorics , 25 (2): 197–217, doi:10.1007/s00373-008-0833-5, MR 2511878, S2CID 2209541

[gethner-10] Gethner, Ellen (2018), "To the Moon and beyond", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi:10.1007/978-3-319-97686-0_11, MR 3930641

[garey-johnson-so-11] Garey, M.; Johnson, D.; So, Hing (October 1976), "An application of graph coloring to printed circuit testing", IEEE Transactions on Circuits and Systems, 23 (10): 591–599, doi:10.1109/tcs.1976.1084138

[stewart-12] Stewart, Ian (April 1993), "The rise and fall of the Lunar M-pire", Mathematical Recreations, Scientific American , 268 (4): 120–121, Bibcode:1993SciAm.268d.120S, doi:10.1038/scientificamerican0493-120, JSTOR 24941454

[jr-variations-13] Jackson, Brad; Ringel, Gerhard (2000), "Variations on Ringel's earth-moon problem", Discrete Mathematics , 211 (1–3): 233–242, doi:10.1016/S0012-365X(99)00278-2, MR 1735339

[alekseev-goncakov-14] Alekseev, V. B.; Gončakov, V. S. (1976), "The thickness of an arbitrary complete graph", Matematicheskii Sbornik , New Series, 101 (143): 212–230, Bibcode:1976SbMat..30..187A, doi:10.1070/SM1976v030n02ABEH002267, MR 0460162

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]