**Hadwiger-Nelson Problem**. Let G be the infinite graph with all points of the plane as vertices and having xy as an edge if and only if the points x and y have distance 1. What is the chromatic number of G? It is known to be at least four and at most seven.**Ringel's Circle Problem**. Let C be a set of circles in the plane. The circles may be of different sizes, and they may overlap; however, no three circles in C can have a common tangent. Let G be the graph with vertices C and edges C_{i}C_{j}for circles C_{i}and C_{j}having a common tangent. Is there an upper bound on the chromatic number of G? If so, it must be at least five.**Sachs' Unit-Sphere Problem**. Let M be a set of unit spheres in R^{n}such that no two have interior points in common. Let G be a graph with vertex set M and edges xy whenever spheres x and y touch. What is the maximum chromatic number for these graphs?**Sphere Colorings**. The chromatic number X(S_{r}) of a sphere of radius r in R^{3}is the minimum number of colors possible in a coloring of the points of the sphere in which any two points at unit (chordal) distance apart are colored differently. Is X(S_{r})=4 for all r > 1/2? More generally, in dimension n, is X(S_{r})=n+1 for all n__>__3 and all r > 1/2?**Graphs of Large Distances**. Let S be a finite set of points in R^{d}, let d_{k}be the kth largest distance formed by pairs of points in S, and let G(s,k) be the graph with vertex set S having an edge xy for all x and y in S such that the distance between x and y is at least d_{k}. How large can X(G(S,k)) be as a function of d and k? What about when S is in convex position?

From the Geometry Junkyard,
computational
and recreational geometry.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Last update: .