The Open Problems Project

Next: Problem 45: Smallest Universal Set of Points for Planar Graphs

Previous: Problem 43: General Unfoldings of Nonconvex Polyhedra

Problem 44: 3-Colorability of Arrangements of Great Circles


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.


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].



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.


Posed by Stan Wagon at the CCCG 2002 open-problem session.


arrangements; coloring; polyhedra

Entry Revision History

E. Demaine & J. O’Rourke, 28 Aug. 2002.



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.


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


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


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