Level B · Reproducible Graph theory P-constant-27b-maximum-chromatic-number-of-biplanar-graphs
Maximum Chromatic Number of Biplanar Graphs
C_27b is the highest possible chromatic number for any biplanar graph.
From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.
Start working on it Submit a claim Follow
Cite
@misc{cairn-constant-27b-maximum-chromatic-number-of-biplanar-graphs,
title = {Maximum Chromatic Number of Biplanar Graphs},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/constant-27b-maximum-chromatic-number-of-biplanar-graphs}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
} Also: CITATION.cff · Atom feed of results
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
Description of constant
is the highest possible chromatic number for any biplanar graph.
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. |
Additional comments and links
- The value of this constant is the solution to the Earth Moon Problem.
- Conjectured to be 11 by Gethner [G2018].
References
- [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.
What counts as progress
- A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
- A formal proof (Lean) of a known bound, or a precise error in a claimed one.
- New references for the tables above (literature claims).
Source and licence
Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.