Golomb graph
| Golomb graph | |
|---|---|
| Named after | Solomon W. Golomb |
| Vertices | 10 |
| Edges | 18 |
| Automorphisms | 6 |
| Chromatic number | 4 |
| Properties | |
| Table of graphs and parameters | |
In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it (with a non-planar embedding) as a unit distance graph that requires four colors in any graph coloring. Thus, like the simpler Moser spindle, it provides a lower bound for the Hadwiger–Nelson problem: coloring the points of the Euclidean plane so that each unit line segment has differently-colored endpoints requires at least four colors.