The Golomb graph is a unit-distance graph
discovered around 1960-1965 by Golomb (Soifer 2008, p. 19).
It is implemented in the Wolfram Language
A non-unit-distance planar embedding is illustrated above.
The Golomb graph has chromatic number 4 (as does the Moser spindle), meaning the chromatic number
of the plane must be at least four, thus establishing a lower bound on the Hadwiger-Nelson
problem. After a more than 50-year gap, the first unit-distance
graph raising this bound (the de Grey graph with
chromatic number 5) was constructed by de Grey
See alsode Grey Graph
, Hadwiger-Nelson Problem
, Moser Spindle
Explore with Wolfram|Alpha
Referencesde Grey, A. D. N. J. "The Chromatic Number of the Plane Is at Least 5." Geombinatorics 28, No. 1,
18-31, 2018.Soifer, A. The
Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its
Creators. New York: Springer, pp. 19-20, 2008.itnik,
A.; Horvat, B.; and Pisanski, T. "All Generalized Petersen Graphs are Unit-Distances
Graphs." J. Korean Math. Soc. 49, 475-491, 2012.
Cite this as:
Weisstein, Eric W. "Golomb Graph." From
MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GolombGraph.html