3-colorability of great-circle arrangements
Needs verification: A solution is claimed (Cahit, 2004); held until the record of the claim is listed here.
Consider a finite arrangement of great circles on the sphere in which no three circles pass through a common point. Its arrangement graph has a vertex for each point where two circles cross and an edge for each arc of a circle joining two consecutive crossing points; under the assumption above it is $4$-regular.
Koester showed that arrangement graphs of circles in the plane, or of arbitrary circles on the sphere, can need four colors, so what matters here is that the circles are great. Aichholzer verified that the arrangement graphs of up to $11$ great circles are all $3$-colorable; Wagon gives further details.
Problem. Are the faces of every zonohedron, viewed as a planar map, properly $3$-colorable? Equivalently, is the arrangement graph of every such arrangement of great circles vertex $3$-colorable?
Source: Wagon (zonohedron form, from Sibley and Wagon (2000)); Felsner, Hurtado, Noy and Streinu (2000) (arrangement form); posed by Wagon at the CCCG 2002 open-problem session; Problem 44 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- arrangements of great circles, graph coloring, The Open Problems Project, zonohedra
References
@article{sibley2000,
author = {Sibley, Thomas and Wagon, Stan},
title = {Rhombic {P}enrose tilings can be 3-colored},
journal = {American Mathematical Monthly},
volume = {106},
year = {2000},
pages = {251--253}
}
@inproceedings{felsner2000,
author = {Felsner, Stefan and Hurtado, Ferran and Noy, Marc and Streinu, Ileana},
title = {Hamiltonicity and colorings of arrangement graphs},
booktitle = {11th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA)},
year = {2000},
pages = {155--164}
}
@article{koester1990,
author = {Koester, G.},
title = {4-critical, 4-valent planar graphs constructed with crowns},
journal = {Math. Scand.},
volume = {67},
year = {1990},
pages = {15--22}
}
@inproceedings{wagon2002,
author = {Wagon, Stan},
title = {A Machine Resolution of a Four-Color Hoax},
booktitle = {Proc. 14th Canad. Conf. Comput. Geom.},
year = {2002},
pages = {181--193}
}
@inproceedings{demaine2003cccg2002,
author = {Demaine, Erik D. and O'Rourke, Joseph},
title = {Open Problems from {CCCG} 2002},
booktitle = {Proceedings of the 15th Canadian Conference on Computational Geometry},
address = {Halifax, Canada},
year = {2003},
pages = {178--181},
url = {https://erikdemaine.org/papers/CCCG2002Open/}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01090, "3-colorability of great-circle arrangements", clopen.solutions.