TOPICS
Search

Golomb Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
GolombGraph

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 as GraphData["GolombGraph"].

GolombGraphEmbeddings

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 (2018).

See also

de Grey Graphs, Hadwiger-Nelson Problem, Moser Spindle, Unit-Distance Graph

Explore with Wolfram|Alpha

References

de 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

Subject classifications