Geometric Graph Coloring Problems
These problems have been extracted from "Graph Coloring Problems", T. Jensen and B. Toft, Wiley 1995. See that book (specifically chapter 9, on geometric and combinatorial graphs) or its online archives for more information about them.- 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 CiCj for circles Ci and Cj 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 Rn 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(Sr) of a sphere of radius r in R3 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(Sr)=4 for all r > 1/2? More generally, in dimension n, is X(Sr)=n+1 for all n > 3 and all r > 1/2?
Graphs of Large Distances. Let S be a finite set of points in Rd, let dk 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 dk. How large can X(G(S,k)) be as a function of d and k? What about when S is in convex position?