What does this research mean for the field?

All known 10-chromatic candidate graphs for Ringel's Earth-Moon problem are non-biplanar, exhausting the known candidate space and providing evidence that the maximum chromatic number of thickness-two graphs is 9. Novelty: ClaimNovelty.NOVEL_FINDING. Consensus alignment: ConsensusAlignment.CHALLENGES_CONSENSUS.

What question did this study set out to answer?

Resolve bounds on Ringel's Earth–Moon problem by determining whether graphs of thickness two can require 10 or more colors, and formally certify critical biplanar graph families.

August 28, 2026Open Access

The Earth–Moon problem: a certified corpus of nine-critical biplanar graphs, the exhaustion of the known χ = 10 candidates, and the status of χ₂

View Full Paper

Ask AI

Bookmark

Authors

DPDigvijay PatilUniversity at Buffalo, State University of New York

Discussion

Member takes

Implication

Computational study reveals non-biplanarity across all known 10-chromatic candidate graphs, suggesting that nine colors suffice for graphs of thickness two.

Key Points

Resolve bounds on Ringel's Earth–Moon problem by determining whether graphs of thickness two can require 10 or more colors, and formally certify critical biplanar graph families.
Applied SAT-modulo-symmetries refutations with drat-trim proof verification alongside combinatorial counting arguments to test graph biplanarity and criticality.
Formalized the lower bound χ₂ ≥ 9 and graph degeneracy machinery in the Lean interactive theorem prover.
Constructed and certified 241 biplanar graphs using Hajós sums and algorithmic edge-swap searches.
Excluded every named 10-chromatic candidate graph from biplanarity, including C₅(4,4,4,4,3), K₃+D₇, CAND-A, and the entire C_m ⊠ K_t family.
Established that any hypothetical 10-chromatic biplanar graph must possess at least 17 vertices unconditionally (n ≥ 17) and at least 19 vertices modulo five open SAT instances.
Refuted the conjecture that every nine-critical biplanar graph satisfies e > 5n − 6 by constructing a 21-vertex, 99-edge counterexample via Hajós sum.

Cite This Study

Digvijay Patil (2026) studied this question.

synapsesocial.com/papers/6a916ea0d15324a1df3aa879 https://doi.org/10.5281/zenodo.22103613

View Full Paper

Ask AI

Bookmark

Implication

Computational study reveals non-biplanarity across all known 10-chromatic candidate graphs, suggesting that nine colors suffice for graphs of thickness two.

The Earth–Moon problem: a certified corpus of nine-critical biplanar graphs, the exhaustion of the known χ = 10 candidates, and the status of χ₂

Discussion

Member takes

Implication

Key Points

Cite This Study

The Earth–Moon problem: a certified corpus of nine-critical biplanar graphs, the exhaustion of the known χ = 10 candidates, and the status of χ₂

Discussion

Member takes

Implication

Key Points

Cite This Study

Also Consider

Also Consider