TOPICS
Search

Voronov-Neopryatnaya-Dergachev Graphs


VoronovNeopryatnayaDergachevGraphs

The Voronov-Neopryatnaya-Dergachev graphs are two tetahedron-free (but not triangle-free 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 with unit egde lengths.

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

de Grey (2026) subsequenctly constructed a 61-vertex graph with chromatic number 5 that has a unit-distance embedding in R^3 and is tetrahedron-free.


See also

de Grey Graphs, Hadwiger-Nelson Problem, Unit-Distance Embedding, Unit-Distance Graph

Explore with Wolfram|Alpha

References

de Grey, A. D. N. J. "A 5-Chromatic, Triangle-Free Unit-Distance Graph in R^3 With 61 Vertices." Geombinatorics 35, 2026.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.

Referenced on Wolfram|Alpha

Voronov-Neopryatnaya-Dergachev Graphs

Cite this as:

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

Subject classifications