Geometric Graph Coloring Problems

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_iC_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 \(\mathbb{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 \(\chi(S_r)\) of a sphere of radius \(r\) in \(\mathbb{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 \(\chi(S_r)=4\) for all \(r > \tfrac12\)? More generally, in dimension \(n\), is \(\chi(S_r)=n+1\) for all \(n\ge 3\) and all \(r > \tfrac12\)?

Graphs of Large Distances

Let \(S\) be a finite set of points in \(\mathbb{R}^d\), let \(d_k\) be the \(k\)th 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 \(\chi(G(s,k))\) be as a function of \(d\) and \(k\)? What about when \(S\) is in convex position?