Hochberg-O'Donnell Star Graph

Author

Eric W. Weisstein
July 26, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/Hochberg-ODonnellStarGraph.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/Hochberg-ODonnellStarGraph.html.

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

Figure

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

Sources

MR1380143
Hochberg, Robert(1-RTG-CS); O'Donnell, Paul(1-RTG)
Some 4-chromatic unit-distance graphs without small cycles. 
Geombinatorics 5 (1996), no. 4, 137–141. 
?

Soifer

Soifer in Nash, p. 455

Graphic

g=GraphData[gn="HochbergODonnellStarGraph"]

GraphData[gn,"EmbeddingClasses"]

dist=EuclideanDistance@@@With[{v=GraphData[gn,"VertexCoordinates"]},GraphData[gn,"Edges","List"]/.i_Integer:>v[[i]]]

Through[{Min,Max}[dist]]

Histogram[dist]

coloring=FindVertexColoring[g,Method->"Brelaz"]

VertexColoringQ[g,coloring]

GraphicsRow[GraphData[gn,"Graph","All"]/.g_System`Graph:>SetProperty[g,{System`VertexStyle->MapIndexed[#2[[1]]->{Red,Yellow,Green,Blue}[[#]]&,coloring],
VertexSize->.8}]]

GraphData[gn,"Girth"]

GraphData[gn,"CyclePolynomial"]

GraphData[gn,"ChromaticNumber"]

GraphData[gn,"MinimumVertexColoring"]

Embeddings

GraphData["HochbergODonnellStarGraph","StandardName"]

Primary

GraphData["HochbergODonnellStarGraph"]//StyleGraphs

All

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

Inexact

Select[GraphData["HochbergODonnellStarGraph","Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData["HochbergODonnellStarGraph","EdgeList"]]

Default embedding

GraphPlot@GraphData["HochbergODonnellStarGraph","Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData["HochbergODonnellStarGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["HochbergODonnellStarGraph","Graph","Degenerate"]

Bilateral

GraphData["HochbergODonnellStarGraph","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["HochbergODonnellStarGraph","Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["HochbergODonnellStarGraph"],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["HochbergODonnellStarGraph"],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData["HochbergODonnellStarGraph","Planar"]

GraphData["HochbergODonnellStarGraph","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["HochbergODonnellStarGraph",{"RCN","CN"}]

GraphData["HochbergODonnellStarGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["HochbergODonnellStarGraph"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["HochbergODonnellStarGraph"],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["HochbergODonnellStarGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData["HochbergODonnellStarGraph","V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData["HochbergODonnellStarGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["HochbergODonnellStarGraph","Graph","Circulant"]//StyleGraphs

Halin

GraphData["HochbergODonnellStarGraph","Halin"]

GraphData["HochbergODonnellStarGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["HochbergODonnellStarGraph","Rigid"]

GraphData["HochbergODonnellStarGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["HochbergODonnellStarGraph","Flexible"]

GraphData["HochbergODonnellStarGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["HochbergODonnellStarGraph","LCF"]

GraphData["HochbergODonnellStarGraph","LCFSignature"]

GraphData["HochbergODonnellStarGraph","Graph","LCF"]//StyleGraphs

Planar

GraphData["HochbergODonnellStarGraph","Planar"]

GraphData["HochbergODonnellStarGraph","Graph","Planar"]//StyleGraphs

UnitDistance

GraphData["HochbergODonnellStarGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["HochbergODonnellStarGraph"],Debug->True]//Timing

GraphData["HochbergODonnellStarGraph","Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData["HochbergODonnellStarGraph","Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData["HochbergODonnellStarGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["HochbergODonnellStarGraph","VertexList"],GraphData["HochbergODonnellStarGraph","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData["HochbergODonnellStarGraph","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["HochbergODonnellStarGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["HochbergODonnellStarGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{"HochbergODonnellStarGraph",l=FindSubgraphUnitDistanceEmbedding[GraphData["HochbergODonnellStarGraph"],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData["HochbergODonnellStarGraph","Matchstick"]

GraphData["HochbergODonnellStarGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["HochbergODonnellStarGraph","Edges"]]

3D All

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

3D UnitDistance

GraphData["HochbergODonnellStarGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["HochbergODonnellStarGraph","Polyhedral"]

GraphData["HochbergODonnellStarGraph","Graph",{"3D","Polyhedron"}]

Construction

Soifer, pp. 124-126

Geocombinatorics V(4), 137-141

Ramsey Theory: Yesterday, Today, and Tomorrow
edited by Alexander Soifer, pp. 140-141

Soifer, A.  ``The Hadwiger-Nelson Problem.''  In \titleisbn{Open Problems in Mathematics}{3319321609} (Ed.\ J.~F.~Nash, Jr.\ and M.~Th.~Rassias).  Switzerland: Springer, p.~445, 2016.\par

Girth 5, 4-chromatic, unit-distance of order 45

v0={{81.37749565972226`,745.2639671148255`},{245.03328387435405`,507.65192738614337`},{281.50316184189285`,459.017159237726`},{309.2956385255169`,356.2436712693798`},{333.5840979287791`,370.466345183301`},{297.2712396035207`,14.370589066537377`},{561.3534853439924`,116.30939367328801`},{613.6492904150518`,132.63943647044562`},{712.3567960675066`,135.20133589712532`},{708.2990779433142`,164.82846313791993`},{433.9031209625324`,343.69862827034876`},{493.97553042231925`,470.0002700056523`},{616.4260588259045`,473.3224750686368`},{649.044823461725`,490.47067284399213`},{707.7371129077844`,481.1156078407621`},{668.6722787467702`,357.5328851744184`},{763.5038784924097`,264.48635083575573`},{1023.7680676679588`,16.494486333171835`},{1012.5700879158594`,315.36071493459303`},{1009.0578064437987`,381.55689044331393`},{825.2208621002909`,500.8091766593991`},{701.1009669735143`,520.5523306282299`},{725.1415006258077`,583.3519233486757`},{691.4235984940248`,580.6164758963178`},{602.0711578447999`,535.4113473029715`},{579.419008397933`,556.418922601744`},{629.2520843427004`,595.0126978359173`},{645.6399764817509`,630.3338531572997`},{407.3502730337533`,703.3975719678616`},{400.72239129118225`,820.7077731346898`},{382.03705385981925`,841.6409707081717`},{537.8088031936371`,688.315422117248`},{753.3885078528749`,707.7775935683138`},{949.5804187863375`,576.3108320211562`},{1018.3384937217379`,482.0494615027453`},{1050.9903151243543`,477.23143774224786`},{1245.0831213662793`,748.7927769702841`},{978.0836159560727`,832.3520192385334`},{913.4328442950584`,849.8886340237402`},{823.212663517442`,887.7551603884043`},{719.0425271519705`,847.706887415213`},{461.98484435562034`,893.5318303859818`},{839.2865163719317`,918.0599513485141`},{496.80188398336577`,952.3150259407298`},{651.1935133034563`,1193.0839868984172`}};

Length[v0]

d=EuclideanDistance@@v0[[{18,10}]]

v=v0/348.60242706068397`;

EuclideanDistance@@v[[#]]&/@{{45,42},{41,45},{1,30},{37,39},{1,3},{1,30}}

e=UnitEdges[v]

remove=Sort/@{{4,6},{7,5},{10,19},{2,30},{24,39},{5,29},{35,38},{27,42},{23,36},{9,15},{26,31},{28,43},{23,25},{23,36},{15,41},{36,15},{9,13},{8,13},{2,25},{43,23}};
add=Sort/@{{1,30},{6,8},{18,20},{7,12},{17,18},{1,29},{2,31},{31,41},{34,43},{39,21},{4,29},{36,38},{20,23},{12,30},{14,9},{14,41},{5,16},{11,29},{17,34},{11,32},{21,38},{12,21},{3,13},{8,15},{7,13},{41,21},{41,15},{33,16},{5,14},{2,26},{43,24}};
e2=Union[add,Complement[e,remove]]

Complement[Flatten[Select[e2,!FreeQ[#,40]&]],{40}]

g=System`Graph[Range[45],UndirectedEdge@@@e2,VertexCoordinates->v,VertexLabels->"Name",VertexSize->.6]

Girth[CombinatoricaGraph[g]]

System`FindCycle[g,{3,4},All][[All,All,1]]

d=VertexDegree[g]

Tally[Sort[d]]

colorrules={1->Red,2->Orange,3->Green,4->Yellow,5->Purple,6->Blue,7->Hue[.5]};

styles=MapIndexed[Style[#2[[1]],#/.colorrules]&,d];

Legended[HighlightGraph[g,styles,ImageSize->600],SwatchLegend@@Transpose[List@@@Reverse/@colorrules]]

MyFindVertexColoring[g,Method->"Brelaz"]

FindVertexColoring[GraphData["HochbergODonnellStarGraph"]]

<<IGraphM`

IGMinimumVertexColoring[GraphData["HochbergODonnellStarGraph"]]//Timing

Through[{VertexCount,EdgeCount}[g]]

v=GraphEmbedding[CenterGraph[GraphData["HochbergODonnellStarGraph"]]];

(groups=(SortBy[#,#[[2]]&]&/@SplitBy[SortBy[MapIndexed[{Norm[#],Mod[ArcTan@@#,2Pi],#2[[1]]}&,Round[10v]],First],First])[[All,All,3]])//Column

g=CenterGraph[GraphData["HochbergODonnellStarGraph"]]

Exactify

Show[g=CenterGraph[UnitDistanceEmbeddingRefine@GraphData["HochbergODonnellStarGraph"]],Axes->True]

EdgeLengths[g]

v=GraphEmbedding[g];

(groups=(SortBy[#,#[[2]]&]&/@SplitBy[SortBy[MapIndexed[{Norm[#],Mod[ArcTan@@#,2Pi],#2[[1]]}&,Round[5v]],First],First])[[All,All,3]])//Column

GraphData["HochbergODonnellStarGraph","Graph","Labeled"]

groups={{24,27,25,14,22},{23,28,26,13,15},{33,32,12,16,21},{34,41,29,11,17},
{40,30,5,10,35},{39,42,3,8,20},{43,31,4,9,36},
{38,44,2,7,19},{37,45,1,6,18}};
HighlightGraph[GraphData["HochbergODonnellStarGraph"],groups]

Union@@groups==Range[45]

v=GraphEmbedding[GraphData["HochbergODonnellStarGraph"]];

(Norm/@v[[#]])&/@groups

as=Mean/@%

qs=ArcTan@@@v[[groups[[All,1]]]]

Graphics[Point[vexact=Flatten[Table[as[[i]]Through[{Cos,Sin}[qs[[i]]+2Pi j/5]],{i,9},{j,0,4}],1]]]

g=Graph[Range[45],UnitEdges[vexact,Tolerance->.03],VertexCoordinates->vexact]

EdgeCount[g]

GraphData["HochbergODonnellStarGraph","M"]

v=vexact[[InversePermutation[Flatten[groups]]]]

RecognizeGraph[g]

g=Graph[Range[45],GraphData["HochbergODonnellStarGraph","Edges"],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

So not perfect 5-fold symmetry?

EdgeLengths[g]

g1=UnitDistanceEmbeddingRefine[g]

EdgeLengths[g1]

g=g1

GraphData

GraphDataString

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

WriteString[file,GraphDataString[
g,
"StandardName"->"HochbergODonnellStarGraph",
"Name"->"Hochberg\[Hyphen]O'Donnell star graph",
"EmbeddingClasses"->{"Primary"}
]]

Close[file]