Next: Problem 45: Smallest Universal
Up: The Open Problems Project
Previous: Problem 43: General Unfoldings
Problem 44: 3Colorability of Arrangements of Great Circles
 Statement
 Is every zonohedron face 3colorable 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 3colorable?
(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 4regular.
 Origin
 The zonohedronface 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 3colorable by Oswin Aichholzer (August, 2002).
See [Wag02] for more details.
 Appearances
 Posed by Stan Wagon at the CCCG 2002 openproblem 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. ACMSIAM Symp. Discrete Algorithms (SODA), pages
155164, January 2000.
 Koe90

G. Koester.
4critical, 4valent planar graphs constructed with crowns.
Math. Scand., 67:1522, 1990.
 SW00

Thomas Sibley and Stan Wagon.
Rhombic Penrose tilings can be 3colored.
American Mathematics Monthly, 106:251253, 2000.
 Wag02

Stan Wagon.
A machine resolution of a fourcolor hoax.
In Proc. 14th Canad. Conf. Comput. Geom., pages 181193,
August 2002.
Next: Problem 45: Smallest Universal
Up: The Open Problems Project
Previous: Problem 43: General Unfoldings
The Open Problems Project  December 04, 2015