next up previous
Next: Problem 45: Smallest Universal Up: The Open Problems Project Previous: Problem 43: General Unfoldings


Problem 44: 3-Colorability of Arrangements of Great Circles

Statement
Is every zonohedron face 3-colorable when viewed as a planar map? An equivalent question, under a different guise, is the following: is the arrangement graph of great circles on the sphere always vertex 3-colorable? (The arrangement graph has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points.) Assume that no three circles meet at a point, so that this arrangement graph is 4-regular.
Origin
The zonohedron-face version is due to Stan Wagon, deriving from the work in [SW00]. The origin of the arrangement guise of the problem is [FHNS00].
Status/Conjectures
Open.
Partial and Related Results
Arrangement graphs of circles in the plane, or general circles on the sphere, can require four colors [Koe90]. The key property in this problem is that the circles must be great. All arrangement graphs of up to 11 great circles have been verified to be 3-colorable by Oswin Aichholzer (August, 2002). See [Wag02] for more details.
Appearances
Posed by Stan Wagon at the CCCG 2002 open-problem session.
Categories
arrangements; coloring; polyhedra
Entry Revision History
E. Demaine & J. O'Rourke, 28 Aug. 2002.

Bibliography

FHNS00
Stefan Felsner, Ferrán Hurtado, Marc Noy, and Ileana Streinu.
Hamiltonicity and colorings of arrangement graphs.
In 11th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), pages 155-164, January 2000.

Koe90
G. Koester.
4-critical, 4-valent planar graphs constructed with crowns.
Math. Scand., 67:15-22, 1990.

SW00
Thomas Sibley and Stan Wagon.
Rhombic Penrose tilings can be 3-colored.
American Mathematics Monthly, 106:251-253, 2000.

Wag02
Stan Wagon.
A machine resolution of a four-color hoax.
In Proc. 14th Canad. Conf. Comput. Geom., pages 181-193, August 2002.


next up previous
Next: Problem 45: Smallest Universal Up: The Open Problems Project Previous: Problem 43: General Unfoldings
The Open Problems Project - December 04, 2015