Misplaced Pages

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

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. 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; the four-color theorem evaded proof until 1976. 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 ${\displaystyle m}$ of distinct regions on the Earth (a home country and ${\displaystyle m-1}$ colonies). As Heawood showed for ${\displaystyle m=2}$, and Ringel later proved with Jackson in 1984 for ${\displaystyle m>2}$, ${\displaystyle 6m}$ colors are necessary and sufficient. 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. In a formulation of Martin Gardner, the colonies are instead on Mars.

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? Ringel proved that the number of colors needed was at least 8 and at most 12, conjecturing that 8 was the correct answer.

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.

Bounds

A biplanar graph on ${\displaystyle n}$ vertices has at most ${\displaystyle 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.

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. This construction, by Thom Sulanke in 1974, disproved the conjecture of Ringel that 8 colors would always suffice. Subsequently, an infinite family of biplanar 9-critical graphs (minimal graphs that require nine colors) has been constructed.

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 ${\displaystyle 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 ${\displaystyle 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.

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.

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. Maps with one planet and multiple regions per country give Heawood's empire problem. 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 ${\displaystyle t\geq 3}$, and the corresponding ${\displaystyle t}$-planet maps, the chromatic number is at most ${\displaystyle 6t}$ by the same degeneracy argument used in the Earth–Moon problem. As well, for ${\displaystyle t\geq 3}$, a complete graph with ${\displaystyle 6t-2}$ vertices has thickness ${\displaystyle t}$, showing some of these graphs require ${\displaystyle 6t-2}$ colors. Thus, in this case, the upper and lower bounds are within two colors of each other.

References

1. ^ Ringel, Gerhard (1959), Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, Berlin: VEB Deutscher Verlag der Wissenschaften, MR 0109349
2. ^ 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
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
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
5. Heawood, P. J. (1890), "Map-Colour Theorem", Quarterly Journal of Mathematics, Oxford, vol. 24, pp. 332–338
6. ^ 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
7. ^ 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
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
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
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, ISBN 978-3-319-97684-6, MR 3930641
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
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
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
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

External links

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

• Graph coloring
• Unsolved problems in graph theory