Hochberg-O'Donnell Fish Graph

Author

Eric W. Weisstein
August 24, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Hochberg-ODonnellFishGraph.nb.

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

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

Graphic

GraphData["HochbergODonnellFishGraph"]//StyleGraphs

GraphData["HochbergODonnellFishGraph",{"V","M"}]

GraphData["HochbergODonnellFishGraph","TriangleCount"]

Smallest triangle-free UD graphs with χ == 4 and girth 4

Soifer 2016, p. 445

Exoo-Ismailescu 17-, 19-, and 21-node graphs are smaller

UnitDistance

Grid[ReverseSort[GraphData[#,{"V","#"}]&/@Select[GraphData[{"UnitDistance","TriangleFree"}],GraphData[#,"ChromaticNumber"]===4&&GraphData[#,"Girth"]==4&]],Dividers->All,Alignment->Left]

All

Grid[Sort[GraphData[#,{"V","#"}]&/@Select[GraphData["TriangleFree"],GraphData[#,"ChromaticNumber"]===4&&GraphData[#,"Girth"]==4&]],Dividers->All,Alignment->{{Decimal,Left}}]

Embeddings

GraphData["HochbergODonnellFishGraph","StandardName"]

Primary

GraphData["HochbergODonnellFishGraph"]//StyleGraphs

Default embedding

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

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

RecognizeGraph[g]

All

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

Circulant

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

Halin

GraphData["HochbergODonnellFishGraph","Halin"]

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

LCF

GraphData["HochbergODonnellFishGraph","LCF"]

GraphData["HochbergODonnellFishGraph","LCFSignature"]

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

Planar

GraphData["HochbergODonnellFishGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

CrossingNumber[GraphData["HochbergODonnellFishGraph"],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData["HochbergODonnellFishGraph"],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData["HochbergODonnellFishGraph"],"CrossingNumber"->9]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

UnitDistance

GraphData["HochbergODonnellFishGraph","UnitDistance"]

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

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

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

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

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

UD exact construction

Embedding from Ed Pegg, Jr.
Dec 14, 2017

The smallest known unit-distance triangle-free graph with chromatic number 4.

fish={{0,0},{-(1/2),-(1/2)},{-(1/2),(1/2)},{(1/2),-(1/2)},{(1/2),(1/2)},{-(1/4),(1/4) (2+(Sqrt[7]))},{(1/4) (-2+(Sqrt[7])),-(1/4)},{(1/4) (-2+(Sqrt[7])),(1/4)},{-(1/4),(1/4) (-2-(Sqrt[7]))},{(1/4) (1+(Sqrt[7])),(1/4) (-1+(Sqrt[7]))},{(1/4) (-1-(Sqrt[7])),(1/4) (-1+(Sqrt[7]))},{(1/4) (1+(Sqrt[7])),(1/4) (1-(Sqrt[7]))},{(1/4) (-1-(Sqrt[7])),(1/4) (1-(Sqrt[7]))},{Root[-319-216 #1+1824 ((#1)^2)+576 ((#1)^3)-3072 ((#1)^4)+2048 ((#1)^6)&,2],Root[-319+216 #1+1824 ((#1)^2)-576 ((#1)^3)-3072 ((#1)^4)+2048 ((#1)^6)&,1]},{Root[-319-216 #1+1824 ((#1)^2)+576 ((#1)^3)-3072 ((#1)^4)+2048 ((#1)^6)&,2],Root[-319-216 #1+1824 ((#1)^2)+576 ((#1)^3)-3072 ((#1)^4)+2048 ((#1)^6)&,4]},{Root[13+456 #1-1728 ((#1)^2)-1600 ((#1)^3)+4608 ((#1)^4)+6144 ((#1)^5)+2048 ((#1)^6)&,3],Root[13-456 #1-1728 ((#1)^2)+1600 ((#1)^3)+4608 ((#1)^4)-6144 ((#1)^5)+2048 ((#1)^6)&,4]},{Root[13+456 #1-1728 ((#1)^2)-1600 ((#1)^3)+4608 ((#1)^4)+6144 ((#1)^5)+2048 ((#1)^6)&,3],Root[13+456 #1-1728 ((#1)^2)-1600 ((#1)^3)+4608 ((#1)^4)+6144 ((#1)^5)+2048 ((#1)^6)&,1]},{Root[-143-1536 #1-4320 ((#1)^2)+2112 ((#1)^3)+20736 ((#1)^4)+27648 ((#1)^5)+18432 ((#1)^6)&,3],Root[-143+1536 #1-4320 ((#1)^2)-2112 ((#1)^3)+20736 ((#1)^4)-27648 ((#1)^5)+18432 ((#1)^6)&,3]},{Root[-143-1536 #1-4320 ((#1)^2)+2112 ((#1)^3)+20736 ((#1)^4)+27648 ((#1)^5)+18432 ((#1)^6)&,3],Root[-143-1536 #1-4320 ((#1)^2)+2112 ((#1)^3)+20736 ((#1)^4)+27648 ((#1)^5)+18432 ((#1)^6)&,2]},{Root[64573-91836 #1-3233592 ((#1)^2)-7450560 ((#1)^3)+23213376 ((#1)^4)+135454464 ((#1)^5)+203751936 ((#1)^6)-48771072 ((#1)^7)-433963008 ((#1)^8)-331776000 ((#1)^9)+127401984 ((#1)^10)+254803968 ((#1)^11)+84934656 ((#1)^12)&,3],Root[64573+91836 #1-3233592 ((#1)^2)+7450560 ((#1)^3)+23213376 ((#1)^4)-135454464 ((#1)^5)+203751936 ((#1)^6)+48771072 ((#1)^7)-433963008 ((#1)^8)+331776000 ((#1)^9)+127401984 ((#1)^10)-254803968 ((#1)^11)+84934656 ((#1)^12)&,7]},{Root[64573-91836 #1-3233592 ((#1)^2)-7450560 ((#1)^3)+23213376 ((#1)^4)+135454464 ((#1)^5)+203751936 ((#1)^6)-48771072 ((#1)^7)-433963008 ((#1)^8)-331776000 ((#1)^9)+127401984 ((#1)^10)+254803968 ((#1)^11)+84934656 ((#1)^12)&,3],Root[64573-91836 #1-3233592 ((#1)^2)-7450560 ((#1)^3)+23213376 ((#1)^4)+135454464 ((#1)^5)+203751936 ((#1)^6)-48771072 ((#1)^7)-433963008 ((#1)^8)-331776000 ((#1)^9)+127401984 ((#1)^10)+254803968 ((#1)^11)+84934656 ((#1)^12)&,2]},{Root[-10487+51300 #1+418536 ((#1)^2)-965952 ((#1)^3)-4849344 ((#1)^4)-3697920 ((#1)^5)+40020480 ((#1)^6)+56733696 ((#1)^7)-135364608 ((#1)^8)-199065600 ((#1)^9)+127401984 ((#1)^10)+254803968 ((#1)^11)+84934656 ((#1)^12)&,2],Root[-10487-51300 #1+418536 ((#1)^2)+965952 ((#1)^3)-4849344 ((#1)^4)+3697920 ((#1)^5)+40020480 ((#1)^6)-56733696 ((#1)^7)-135364608 ((#1)^8)+199065600 ((#1)^9)+127401984 ((#1)^10)-254803968 ((#1)^11)+84934656 ((#1)^12)&,4]},{Root[-10487+51300 #1+418536 ((#1)^2)-965952 ((#1)^3)-4849344 ((#1)^4)-3697920 ((#1)^5)+40020480 ((#1)^6)+56733696 ((#1)^7)-135364608 ((#1)^8)-199065600 ((#1)^9)+127401984 ((#1)^10)+254803968 ((#1)^11)+84934656 ((#1)^12)&,2],Root[-10487+51300 #1+418536 ((#1)^2)-965952 ((#1)^3)-4849344 ((#1)^4)-3697920 ((#1)^5)+40020480 ((#1)^6)+56733696 ((#1)^7)-135364608 ((#1)^8)-199065600 ((#1)^9)+127401984 ((#1)^10)+254803968 ((#1)^11)+84934656 ((#1)^12)&,5]}};

fishlines=Select[Subsets[Range[23],{2}],.999<Quiet@N[EuclideanDistance@@fish[[#]]]<1.001&&RootReduce[Quiet@EuclideanDistance@@fish[[#]]]==1&]

Graphics[{EdgeForm[{Black,Thick}],Thick,Line[fish[[#]]]&/@fishlines,{White,Disk[#,.03]&/@fish},Table[Style[Text[n,fish[[n]]],Bold],{n,1,Length[fish]}]}]

g=System`Graph[fishlines,VertexCoordinates->fish]

VertexCount[g]

Girth[CombinatoricaGraph[g]]

UnitDistanceGraphQ[g]

UnitDistanceGraphQ[g,WorkingPrecision->20]

UnitDistanceGraphQ[g,WorkingPrecision->Infinity]//FullSimplify//Timing

System`FindCycle[g,{3}]

poly=System`ChromaticPolynomial[g,x]

MinValue[{x,poly>0&&x>0},x,Integers]

fishpoly=System`ChromaticPolynomial[System`Graph[#[[1]]\[UndirectedEdge]#[[2]]&/@fishlines],k];
fishpoly/.k-> #&/@Range[3,5]

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData["HochbergODonnellFishGraph","Matchstick"]

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

3D default

Graph3D[GraphData["HochbergODonnellFishGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["HochbergODonnellFishGraph","Polyhedral"]

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

Properties

ChromaticNumber

GraphData[gn,"ChromaticNumber"]

CyclePolynomial

GraphData[gn,"CyclePolynomial"][x]

Flexible

https://math.stackexchange.com/questions/3958839/are-4-chromatic-3-connected-unit-distance-graphs-always-rigid

Import["https://i.stack.imgur.com/Zux3n.gif",{"GIF","Animation"}]

Girth

GraphData[gn,"Girth"]

Laman

LamanGraphQ[GraphData["HochbergODonnellFishGraph"],Debug->True]//Timing

MinimalVertexColoring

GraphData[gn,"MinimumVertexColoring"]

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

VertexColoringQ[g,coloring]

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

Rigid

RigidityAnalysisDiagram[GraphData["HochbergODonnellFishGraph"]]

UnitDistance

g=GraphData[gn="HochbergODonnellFishGraph"]

GraphData[gn,"EmbeddingClasses"]

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

Through[{Min,Max}[dist]]

References

"Not all unit distance 4-chromatic graphs are in . For example, Hochberg–O'Donnell's fish graph has vertices that rely on polynomials of degree 12. An exact solution can be found at the end of the Initialization section"
http://demonstrations.wolfram.com/MoserSpindlesGolombGraphsAndRoot33/

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, 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

GraphData

GraphData

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

WriteString[file,GraphDataString[
g,
"StandardName"->"HochbergODonnellFishGraph",
"Name"->"Hochberg\[Hyphen]O'Donnell fish graph",
"EmbeddingClasses"->{"Integral","MinimalIntegral","Primary","UnitDistance"}
]]

Close[file]