Next: Problem 45: Smallest Universal Set of Points for Planar Graphs
Previous: Problem 43: General Unfoldings of Nonconvex Polyhedra
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].
Open.
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
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.