Three-colouring arrangements of great circles

Draw some great circles on a sphere, no three through a point, and colour the crossing points so that neighbours along a circle get different colours. Four colours always suffice; the conjecture is that three do, and it has been checked by computer for up to 11 circles.

Problem

Let $C_1,\dots,C_n$ be great circles on the unit sphere $S^2$ with no three through a common point (a simple arrangement). Any two great circles cross in two antipodal points. The arrangement graph $G$ has these $n(n-1)$ crossing points as vertices, and an edge for each arc of a circle that joins two consecutive crossing points. $G$ is planar and 4-regular; for $n=3$ it is the octahedron.

Conjecture (Felsner, Hurtado, Noy and Streinu). For every simple arrangement of great circles, the arrangement graph has chromatic number at most 3.

An equivalent form, due to Stan Wagon: the faces of every zonohedron, viewed as a planar map, can be coloured with three colours so that faces sharing an edge differ.

Background

Felsner, Hurtado, Noy and Streinu stated the conjecture in 2000 while studying connectivity, Hamiltonicity and colourings of arrangement graphs [1]; Wagon raised the zonohedron form at the CCCG 2002 open-problem session [2], building on his work with Sibley on 3-colouring rhombic Penrose tilings [4]. By the four colour theorem, or Brooks' theorem, every arrangement graph is 4-colourable, so the question is whether the great-circle condition rules out the fourth colour.

What is known

• Four colours can be needed nearby. Non-simple great-circle arrangements can require four colours, and so can simple arrangements of ordinary circles; Koester (1985) gave one with 7 circles [3].
• Small cases. Aichholzer, Aurenhammer and Krasser verified the conjecture for all arrangements of up to 11 great circles. Chiu, Felsner, Scheucher, Schröder, Steiner and Vogtenhuber re-generated these data and extended the check to all arrangements of up to 11 great-pseudocircles (combinatorial versions that need not be realisable by actual circles) [3].
• A special class. The same authors proved 3-colourability for $\triangle$-saturated pseudocircle arrangements, in which every edge lies on exactly one triangular face, and showed that arrangements of $n$ pairwise intersecting pseudocircles have fractional chromatic number at most $3+O(1/n)$ [3].
• Stronger conjectures. Based on exhaustive experiments, they proposed strengthenings, including that every simple arrangement of $n\ge 7$ great-pseudocircles has an antipodal 3-colouring, in which antipodal points share a colour [3].

What would count as progress

• A counterexample: great circles given by exact rational normal vectors whose arrangement graph is not 3-colourable. A SAT solver confirms non-3-colourability of a graph of this size quickly.
• An exhaustive check for 12 or more great (pseudo)circles, with the enumeration code and the colourings published.
• A proof for a new infinite class of arrangements, or for all of them.

References

1. S. Felsner, F. Hurtado, M. Noy and I. Streinu, Hamiltonicity and colorings of arrangement graphs, Discrete Appl. Math. 154 (2006), 2470–2483; extended abstract in SODA 2000. doi:10.1016/j.dam.2006.04.006
2. S. Wagon, A machine resolution of a four-color hoax, Proc. 14th Canadian Conf. Comput. Geom. (2002), 174–185. cccg.ca
3. M.-K. Chiu, S. Felsner, M. Scheucher, F. Schröder, R. Steiner and B. Vogtenhuber, Coloring circle arrangements: new 4-chromatic planar graphs, European J. Combin. 121 (2024), 103839. doi:10.1016/j.ejc.2023.103839, arXiv:2205.08181
4. T. Sibley and S. Wagon, Rhombic Penrose tilings can be 3-colored, Amer. Math. Monthly 107 (2000), 251–253. doi:10.1080/00029890.2000.12005187

Source

Imported from The Open Problems Project, Problem 44, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.