Chromatic Spindles

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

Color the plane so that no two points of the same color are at distance 1 apart. How many colors are needed? If instead, 3D space is colored, how many colors are needed there? Both are unsolved problems! The chromatic number of the plane is 4, 5, 6, or 7. This question is known as the Hadwiger–Nelson problem. In space, the range of possible values is 6–15.

[more]

This Demonstration uses objects (known as spindles) that determine the lower bounds of these ranges. Drop an equilateral triangle with unit edges onto the plane. The three points are pairwise at distance 1 apart, so the plane requires at least three colors. Is there a larger graph that forces a 4-coloring? Two are shown here, the Moser spindle and the Golomb graph. One difficulty in finding these is that two unit circles can only intersect at two points. Any graph containing (four connected points) or (two points connected to three points) cannot be a part of a planar spindle.

For 3D space, a tetrahedron proves at least four colors are needed. Three 3D spindles forcing a 5-coloring are given. Two were found by Raiskii and Nechushtan. In [3] a method for combining these two spindles into a graph of around 400 vertices is given, which proves that space needs six colors. The third 3D spindle was found by the author. A cluster of 4 tetrahedra each sharing an edge looks like a Pac‐Man. The double Pac‐Man uses two of those.

The chromatic polynomial of each graph is calculated to find the number of colorings for each spindle.

[less]

Contributed by: Ed Pegg Jr (October 2015)
Open content licensed under CC BY-NC-SA


Snapshots


Details

References

[1] Wikipedia. "Hadwiger–Nelson Problem." (Oct 22, 2015) en.wikipedia.org/wiki/Hadwiger% E2 %80 %93 Nelson_problem.

[2] D. Coulson, "A 15-Colouring of 3-Space Omitting Distance One," Discrete Mathematics, 256(1–2), 2002 pp. 83–90. doi:10.1016/S0012-365X(01)00183-2.

[3] O. Nechushtan, "On the Space Chromatic Number," Discrete Mathematics, 256(1–2), 2002 pp. 499–507. doi:10.1016/S0012-365X(00)00406-4.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send