A 1988 paper by C. D. Godsil and J. Zaks [1] states the following result, which is the solution of problem nr. 10769:
``Let G be the graph with the points of the unit sphere in three dimensions as its vertices, and two vertices adjacent if and only if they are orthogonal as unit vectors (i.e., their spherical distance is p/2. The chromatic number of G is four.''
A proof that four colors suffice for G is constructive and rather elementary. Consider first the intersection points of the sphere with the the x-, the y- and the z-axis, colored by green, blue and red, respectively. There are exactly three great circles which pass through two of these three pairs of points. The great circles can be colored with the two colors used on the four points they pass through. The three great circles divide the sphere into eight open octants of equal area. Four octants, say, in the half space z > 0, are colored by the four colors red, white, green and blue. The remaining octants obtain their color from their antipodal octant.
Although the paper is not entirely specific, it is easy to write down an explicit coloring scheme according to the above prescription. Consider spherical coordinates: let q be the angle between the z-axis and the line connecting the origin and the point, and j be the angle between the x-axis and the projection of the line connecting the origin and the point onto the x-y-plane. In terms of these coordinates, an arbitrary point on the unit sphere is given by (q, j, r = 1) º (q,j).
The colors of the cartesian coordinate axes (p/2,0), (p/2,p/2), (0,0) are green, blue and red, respectively.
The color of the octant {(q, j) | 0 < q £ p/2, 0 £ j < p/2} is green.
The color of the octant {(q, j) | 0 £ q < p/2, p/2 £ j £ p} is red.
The color of the octant {(q, j) | 0 < q < p/2, p < j < -p/2} is white.
The color of the octant {(q, j) | 0 < q £ p/2, -p/2 £ j < 0} is blue.
The colors of the points in the half space z < 0 are inherited from their antipodes. This completes the coloring of the sphere.
The fact that three colors are not sufficient is not so obvious. We shall not review Godsil and Zaks' proof based on a paper by A. W. Hales and E. G. Straus [2], but refer to an old result of E. Specker [5] and S. Kochen and E. Specker [4], which is of great importance in the present debate on hidden parameters in quantum mechanics. They have proven that there does not exist a valuation on the one dimensional subspaces of real Hilbert space in three dimensions. (In physics, each subspace is interpreted as physical proposition, and valuations are interpreted as truth assignments.) The nonexistence of valuations is a stronger result than the impossibility to color the sphere appropriately with three colors, since an appropriate coloring of one dimensional linear subspaces with two colors could be immediately obtained from any possible appropriate coloring of the sphere with three colors by just identifying two of the three colors and taking the linear span of the vectors from the origin to the respective points on the sphere. (``Appropriate'' here means: ``points at spherical distance p/2 apart get different colors.'')
Indeed, already in 1967, S. Kochen and E. Specker [4] gave an explicit example (their G3) of a finite point set of the sphere which is colorable by two colors but not by three colors, although they did not mention nor discuss this particular feature.
C. D. Godsil and J. Zaks [1] also proved the following rather unexpected result: The chromatic number of the the subgraphs of G induced by the unit vectors with all coordinates rational (i.e., the rational unit sphere) is three. They gave an explicit construction for which each color class is dense in the sphere.