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.