OpenFrontiers
Join
← Back to the index
OP-12037OpenGraph theory

Maximum Chromatic Number of Biplanar Graphs (C27bC_{27b})

Maximum Chromatic Number of Biplanar Graphs: determine C27bC_{27b} or improve its bounds; the repository records 9 (lower) and 12 (upper).

MSC 05C15 · Coloring of graphs and hypergraphsMSC 05C10 · Planar graphs; geometric and topological aspects of graph theory

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C27bC_{27b} is the highest possible chromatic number for any biplanar graph.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • The value of this constant is the solution to the Earth Moon Problem.
  • Conjectured to be 11 by Gethner [G2018].

References (from the repository page)

  • [G1980] M. Gardner, "The coloring of unusual maps leads into uncharted territory", Mathematical Games, Scientific American, 242 (2): 14–23, doi:10.1038/scientificamerican0280-14.
  • [G2018] E. Gethner, "To the Moon and beyond", in R. Gera, T. W. Haynes, and S. T. Hedetniemi (eds.), Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, 2018, doi:10.1007/978-3-319-97686-0_11, MR 3930641.
  • [R1959] G. Ringel, "Färbungsprobleme auf Flächen und Graphen", Mathematische Monographien, vol. 2, Berlin: VEB Deutscher Verlag der Wissenschaften, 1959, MR 0109349.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 9; best known upper bound 12. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
12 Trivial [R1959] In fact, every biplanar graph has a vertex of degree at most 11.

Known lower bounds

Bound Reference Comments
8 [R1959]
9 Sulanke [G1980] Constructed as the join of a 6-vertex complete graph and a 5-vertex cycle graph.
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Maximum Chromatic Number of Biplanar Graphs ($C_{27b}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.