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?
From the Geometry Junkyard,
computational
and recreational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Last update: .
