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

**Previous:** Problem 43: General Unfoldings of Nonconvex Polyhedra

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

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