Raiskii Graph

Author

Eric W. Weisstein
December 22, 2020

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/RaiskiiGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/RaiskiiGraph.html.

©2020 Wolfram Research, Inc. except for portions noted otherwise

Figure

GraphicsRow[
StyleGraphs[
GraphData["RaiskiiGraph","Graph","All"]
],
Dividers->All
]

Sources

Fig. 5 in 
Discrete Mathematics 256 (2002) 499–507
On the space chromatic number
Oren Nechushtan

D.E. Raĭskiĭ: The realization of all distances in a decomposition of the space IRn in n + 1 parts, Math. Notes 7 (1970) 194–196.

MR0261446

Graphs

2D

GraphData["RaiskiiGraph","Graph","All"]//StyleGraphs

GraphData["RaiskiiGraph","EmbeddingClasses"]

3D

GraphData["RaiskiiGraph","Graph",{"3D","All"}]

GraphData["RaiskiiGraph","EmbeddingClasses3D"]

Construction

https://demonstrations.wolfram.com/ChromaticSpindles/

Three 3D spindles forcing a 5-coloring are given. Two were found by Raiskii and Nechushtan. In [3] a method for combining these two spindles into a graph of around 400 vertices is given, which proves that space needs six colors.

[3] O. Nechushtan, "On the Space Chromatic Number," Discrete Mathematics, 256(1–2), 2002 pp. 499–507. doi:10.1016/S0012-365X(00)00406-4.

v= {{0,1,0},{0,0,0},{Sqrt[3]/2,1/2,0},{(1/(2 (Sqrt[3]))),(1/2),(Sqrt[(2/3)])},{(4/(3 (Sqrt[3]))),(4/3),((2 (Sqrt[(2/3)]))/3)},
{((7 (Sqrt[3]))/32),(1/2),-((3 (Sqrt[69]))/32)},{Root[11881-527040 ((#1)^2)+746496 ((#1)^4)&,4],(4/3),Root[133225-800064 ((#1)^2)+746496 ((#1)^4)&,2]},
{Root[2582449-10475520 ((#1)^2)+9437184 ((#1)^4)&,4],(1/2),Root[34225-3680256 ((#1)^2)+9437184 ((#1)^4)&,3]}};

e=Select[Subsets[Range[Length[v]],{2}],Abs[EuclideanDistance@@v[[#]]-1]<=.01&]//Quiet;

g0=Graph[Range@Length[v],UndirectedEdge@@@e,VertexCoordinates->v]

UnitDistanceGraphEmbeddingQ[g,WorkingPrecision->∞]

ChromaticPolynomial[g][x]

ChromaticNumber[g]

CrossingNumber[g]

GraphPlot[EdgeList[g]]

RecognizeGraph[g]

MemberQ[GraphData[8],{8,11833}]

UnitDistanceGraphQ[g]

g=Graph[Range[8],UndirectedEdge@@@{{1,2},{2,3},{3,4},{4,5},{1,5},{5,6},{4,8},{5,7},{4,7},{1,7},{3,7},{1,6},{3,8},{6,7},{7,8},{2,7},{2,6},{2,8}},VertexCoordinates->{{0,0},{1/2,0},{1,0},{1,1},{0,1},{1/4,1/2},{1/2,1/2},{3/4,1/2}},VertexLabels->"Name"]

IsomorphicGraphQ[g0,g]

ToCommonEdges[g0,g]

GraphData

GraphDataString

file=OpenWrite["~/raiskii.m"]

WriteString[file,GraphDataString[g,
"StandardName"->"RaiskiiGraph",
"Name"->"Raiskii graph",
Debug->True,
TimeConstraint->60
]]

Close[file]