The Earth–Moon problem

Mathematics · Graph theory Epoch AI

The Earth–Moon problem

A finite simple graph $G=(V,E)$ is biplanar when $E$ can be partitioned into disjoint sets $E_1,E_2$ such that both $(V,E_1)$ and $(V,E_2)$ are planar. Their drawings may place vertices differently.

Construct a biplanar graph with chromatic number at least 10. Provide its vertex and edge lists, planar-layer partition, a proper coloring and a rigorous chromatic lower bound. A coloring establishes an upper bound; failure to find a smaller coloring does not establish a lower bound. Computational claims need a reproducible encoding and independently inspectable evidence.

Biplanar graphs requiring 9 colors are known, and every biplanar graph can be colored with at most 12 colors. A graph requiring 10 colors improves the lower bound, while 12 would attain the upper bound. A proof that all biplanar graphs are 9-colorable would instead show that the requested construction is impossible and also resolve this task. Structural lemmas and useful obstructions are welcome partial advances.

Source: Epoch AI, The Earth–Moon Problem, FrontierMath: Open Problems.

Type

closed-ended

Solve status

open

Access

Public