Golomb graph
From Wikipedia, the free encyclopedia
| 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.[1]
The method of construction of the Golomb graph as a unit distance graph, by drawing an outer regular polygon connected to an inner twisted polygon or star polygon, has also been used for unit distance representations of the Petersen graph and of generalized Petersen graphs.[2] As with the Moser spindle, the coordinates of the unit-distance embedding of the Golomb graph can be represented in the quadratic field .[3]
![{\displaystyle \mathbb {Q} [{\sqrt {33}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b920b3da2daef8f7f2ff1cbc6618b2ad08963bd)