Earth-Moon Problem

The Earth--Moon Chromatic-Number Problem

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A finite graph is biplanar, or has thickness at most two, when its edge set can be partitioned into two planar subgraphs on the same vertex set. The two planar drawings need not use the same vertex positions. Determine the supremum of $\chi(G)$ over such graphs. This is an ordinary vertex-colouring problem, not a two-layer drawing-colouring rule. [S1] [S2]

Statement recorded in the supplied source.

What is the maximum chromatic number of biplanar graphs? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Determine the maximum chromatic number of biplanar graphs. [S1]

Short English statement

How many vertex colours can be needed by a graph whose edges can be split into two planar layers?

Research attempt

Status: UNRESOLVED. We prove the elementary bounds $6\le\sup\chi(G)\le12$ for biplanar graphs, refine the upper bound for triangle-free layers, and isolate a critical-graph obstruction that edge counting alone does not eliminate. The bounds are a self-contained baseline, not claimed to be the sharpest known bounds.

Context and chosen attack.

Eppstein [S2], checked 1 October 2026, disproves a conjecture that every two-blowup of a planar graph is biplanar. Thus such blowups cannot be used as an unrestricted source of biplanar constructions. We work instead from a verified edge partition into two planar layers. The drawings of these layers need not share a geometric placement of the vertices; only their abstract vertex set is shared.

A hereditary edge bound.

For a simple planar graph with $v\ge3$ vertices, Euler's formula and the face-length count give $e\le3v-6$. One may first connect components by new plane edges and triangulate if needed; these additions only increase $e$, so the bound holds for disconnected graphs too. If $G=G_1\cup G_2$ is biplanar with disjoint layer edge sets, then \[ e(G)\le6v(G)-12\qquad(v(G)\ge3). \] Every subgraph is also biplanar by restricting the two layers. Consequently each nonempty subgraph on at least three vertices has average degree strictly less than twelve and a vertex of degree at most eleven. Subgraphs on one or two vertices satisfy the same degree conclusion directly.

A complete twelve-colouring algorithm.

Repeatedly remove a vertex of degree at most eleven from the current graph. The hereditary argument guarantees such a vertex at every step. Insert the removed vertices in reverse order, assigning each one a colour among twelve not used by its already inserted neighbours. There are at most eleven such neighbours, so a colour is available. Induction gives a proper twelve-colouring of the original graph.

The removal degrees, not the degrees in the original graph, justify the greedy step. This establishes the upper bound without invoking the four-colour theorem. Independently colouring the layers and taking ordered pairs would give sixteen colours if one imported that theorem, but would not supply the sharper twelve-colour conclusion above.

An explicit six-chromatic biplanar graph.

Take $K_6$ and partition its vertices into three pairs. Put every edge joining different pairs in the first layer. This is $K_{2,2,2}$, the octahedral graph: draw a four-cycle as an equator, one vertex joined to all equatorial vertices inside it, and the other joined to all of them in the outer face. It is planar. Put the three edges within the pairs in the second layer; these form a matching and are planar. The two layers partition all fifteen edges of $K_6$.

Since a complete graph on six vertices requires six distinct vertex colours, this gives the lower bound six. The argument is an exact abstract layer construction. It does not assume the two drawings can simultaneously be drawn without crossings at the same coordinates.

Critical graphs expose the remaining counting gap.

If a graph has chromatic number $r$, it contains an $r$-vertex-critical subgraph $H$: repeatedly delete any vertex whose removal preserves chromatic number $r$. In $H$ every vertex has degree at least $r-1$, because otherwise an $(r-1)$-colouring of $H-v$ extends to $v$. Thus \[ \frac{(r-1)v(H)}2\le e(H)\le6v(H)-12. \] For $r=13$, this is impossible. For $r=12$, it merely requires $v(H)\ge24$; it gives no contradiction for larger order. This shows exactly why the edge-budget argument stops at twelve. Eliminating a possible twelve-chromatic critical graph requires structural information about its two planar layers, not a repeat of the same average-degree estimate.

A more restrictive layer class.

If both planar layers are triangle-free, the planar face count improves to $e_i\le2v-4$ for $v\ge3$. The same hereditary argument gives $e(G)\le4v-8$, a vertex of degree at most seven in every nonempty subgraph, and an eight-colouring. Triangles in the union may still occur using edges from both layers; the hypothesis concerns each layer separately. This refined theorem therefore cannot be applied to an arbitrary biplanar graph unless such a triangle-free decomposition is actually supplied.

Verification and exact remaining gap.

The octahedral layer has twelve edges and its complementary matching has three, accounting for every edge of $K_6$ exactly once. Small subgraphs were handled separately where planar formulas have exceptions. No computational embedding or chromatic-number search is claimed.

The target remains the exact supremum of chromatic number. The proved baseline leaves the integers six through twelve as possible values without asserting that any is best in the literature. The concrete next step is to rule out critical graphs compatible with both planar embeddings or construct a graph needing more colours together with a checkable two-layer decomposition. Biplanarity cannot be inferred just from satisfying its necessary edge bound.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1396 (GRAPH-009), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 D. Eppstein, On the Biplanarity of Blowups, arXiv:2301.09246 $2023$. https://arxiv.org/abs/2301.09246. Bibliographic information from the supplied record.

• S3 Earth-Moon Problem, Graph-theory open problems tracker. https://mlelarge.github.io/graph-conjectures/op/earth_moon_problem/. Bibliographic information from the supplied record.