A 6-Chromatic Unit Distance Graph in Space

Overview

The chromatic number of the n-dimensional Euclidean space is the minimum number of colors with which the entire space can be colored so that every two points one unit apart have different colors. A unit-distance graph in n dimensions is a graph whose vertices are points in the n-dimensional space and whose edges are pairs of points unit-distance apart. Clearly, the chromatic number of an n-dimensional space is at least as large as the chromatic number of some finite unit-distance graph. The chromatic number is greater than or equal to n+1, since every two vertices of an n-dimensional regular simplex of unit side-length require different colors. The spindle construction, ascribed to Moser and Moser for n = 2 and Raiskii for n > 3, uses regular simplices to demonstrate that the chromatic number is greater than or equal to n + 2. In 2002, Nechushtan proved that the chromatic number in 3 dimensions is greater than or equal to 6 and claimed that his proof can be used to construct a unit-distance graph which requires six colors and has no more than 400 vertices. By rotating and transforming Nechushtan’s basic unit-distance graph with chromatic number 5, we construct an explicit unit-distance graph in 3 dimensions with chromatic number 6 that has only 79 vertices and 250 edges. Our methods can be applied to certain 2-deficient, x-chromatic unit-distance graphs in order to construct graphs with chromatic number x+ 1.

Awards (1)

• Fourth Award of $500 $500

Competition history

• ISEF 2017 Mathematics · Entry MATH043T

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.