Earth -Moon問題

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. In mathematical terms, it seeks the chromatic number of biplanar graphs .眾所周知，這個數字至少是9，最多12個。

公式

In the map coloring problem, a collection of 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 have a nonzero length of boundary, they有不同的顏色。 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.根據四種顏色定理，無論給出多少個區域，最多都可以使用最多四種不同的顏色。

取而代之的是，在地球 - 時蒙的問題中，地球上的每個國家都有一個相應的菌落在月球表面，必須給出相同的顏色。這些菌落的邊界可能與地球上邊界的佈置完全不同。必須為每個國家及其殖民地使用相同的顏色來顏色，以便當兩個國家在地球上或月球上共享一個邊界時，它們得到了不同的顏色。林德爾的問題問：無論其邊界如何安排，都需要多少種顏色來確保所有國家都可以塗上顏色？

同樣，一個人可以等效地表達與圖理論中的問題相同的問題，每個國家及其殖民地都有一個頂點，以及國家或殖民地之間的每個鄰接的優勢。 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 Earth adjacencies and the 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.

邊界

Biplanar圖頂點最多有邊緣（平面圖可以擁有的數字是兩倍），從中，它至少有一個頂點，只有11個鄰居。刪除此頂點，遞歸遞歸顏色，然後使用最小的未使用的顏色作為去除的頂點的顏色，從而使最多12種顏色具有顏色；這是圖形退化順序的貪婪著色。因此，Biplanar圖最多需要12種顏色。

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 .這意味著這兩個子圖由一個從一個子圖到另一個子圖的所有可能邊緣連接。所得的圖具有11個頂點，並且需要6種顏色的完整子圖和3種顏色的周期子圖顏色，總體上提供了9種顏色。湯姆·薩蘭克（Thom Sulanke）於1974年由林格爾（Ringel）提出了一種猜想，這種結構總是足以滿足8種顏色。 Subsequently, infinitely many examples of biplanar 9-critical graphs (minimal graphs that require nine colors) have 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 obtained as the strong product of a cycle graph with a clique, and the graph obtained by removing any vertex from 。 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.此外，它們符合雙層圖具有邊緣數量的邊界。然而，它們作為雙帕納爾圖（或地球地圖）的表示仍然難以捉摸。

應用

One application of colorings of biplanar graphs involves testing printed circuit boards for short circuits.這些板中的電導體包括穿越，但可以假定它們的鄰接形成雙翼型圖。塗上此圖後，可以通過添加額外的電路來連接所有具有相同顏色的導體並測試不同顏色對之間的連接來檢測到相鄰導體之間的短電路。有了一定的謹慎，該想法可用於將每個電路所需的測試數量減少到只有四個。

概括

還考慮了該問題的各種概括，包括兩個以上行星的問題版本，或每個行星可以多個區域的國家。特別是厚度圖 （代表兩個以上的行星，但每個行星只有一個區域），更精確（儘管仍然不完整）的結果是已知的。對於這些圖，色數最多是通過在地球 - 幾個月問題中使用的墮落論點。也是如此 ，完整的圖表頂點有厚度 ，顯示其中一些圖需要顏色。因此，在這種情況下，上限和下限在彼此的兩種顏色之內。