Maximum Chromatic Number of Biplanar Graphs
Description of constant
$C_{27b}$ 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.
Contribution notes
Before I opened the pull request adding this file I had Copilot review it.