Moser Spindle

The Moser spindle is the 7-node unit-distance graph illustrated above (Read and Wilson 1998, p. 187). It is sometimes called the Hajós graph (e.g., Bondy and Murty 2008. p. 358), though this term is perhaps more commonly applied to the Sierpiński sieve graph .

It is implemented in the Wolfram Language as GraphData["MoserSpindle"].

A few other (non-unit) embeddings of the Moser spindle are illustrated above.

The Moser spindle has chromatic number 4 (as does the Golomb graph), 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).

---

REFERENCES

Bondy, A. and Murty, U. S. R. Graph Theory. Berlin: Springer-Verlag, 2008.

de Grey, A. D. N. J. "The Chromatic Number of the Plane Is at Least 5." Geombinatorics 28, No. 1, 18-31, 2018.

Moser, L. and Moser, W. "Problem 10." Canad. Math. Bull. 4, 187-189, 1961.

Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.

Soifer, A. "The Hadwiger-Nelson Problem." In Open Problems in Mathematics (Ed. J. F. Nash, Jr. and M. Th. Rassias). Switzerland: Springer, p. 442, 2016.

Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2008.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength