TOPICS
Search

Voronov-Neopryatnaya-Dergachev Graphs


VoronovNeopryatnayaDergachevGraphs

The Voronov-Neopryatnaya-Dergachev graphs are two graphs on 372 and 972 vertices which have unit-distance embeddings with all vertices on a sphere and chromatic number 5. The smaller of these is embedded on the circumsphere of a regular icosahedron with a unit edge length, while the larger is embedded on the circumsphere of a great icosahedron.

These graphs are implemented in the Wolfram Language as GraphData["VoronovNeopryatnayaDergachevGraph372"] and GraphData["VoronovNeopryatnayaDergachevGraph972"], respectively.


See also

Hadwiger-Nelson Problem, Unit-Distance Embedding, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Voronov, V. A.; Neopryatnaya, A. M.; and Dergachev, E. A. "Constructing 5-Chromatic Unit Distance Graphs Embedded in the Euclidean Plane and Two-Dimensional Spheres." Disc. Math. 345, 113106 1-14, 2022.

Cite this as:

Weisstein, Eric W. "Voronov-Neopryatnaya-Dergachev Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Voronov-Neopryatnaya-DergachevGraphs.html

Subject classifications