Mixon Graphs

Author

Eric W. Weisstein
August 16, 2022

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

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

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

Graphic

mixon=GraphData["MixonGraph*"]

ColorGraph[g_Graph]:=Module[{col=FindVertexColoring[g],cols={Red,Green,Yellow,Green,Blue}},
Annotate[g,{EdgeStyle->Directive[LightGray],VertexStyle->MapIndexed[#2[[1]]->cols[[#]]&,col]}]
]

GraphicsRow[Show[ColorGraph[GraphData[#]],PlotLabel->Style[GraphData[#,"Name"],Directive[Black,FontSlant->Italic,FontFamily->"Times"]]]&/@Reverse[mixon],ImageSize->500,Dividers->All]

Table

Print[{#,VertexChromaticNumber[GraphData[#]]//Timing,UnitDistanceGraphEmbeddingQ[GraphData[#],WorkingPrecision->∞]//Quiet//Timing}]&/@mixon;

TextGrid[GraphData[#,{"V","M","Name"}]&/@mixon,Dividers->All]

"MixonGraph1577"

Embeddings

All

GraphData["MixonGraph1577","Graph","All"]//StyleGraphs[#,VertexSize->{"Scaled",.01}]&

Circular

GraphData["MixonGraph1577","Graph","All"]//StyleGraphs[#,VertexSize->{"Scaled",.01}]&

LCF

GraphData["MixonGraph1577","LCF"]

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

Construction

https://asone.ai/polymath/index.php?title=Hadwiger-Nelson_problem

https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/

UPDATE: After the previous update, we wondered which vertices could be removed from the 1585-vertex graph without the graph becoming 4-colorable. After an exhaustive search, we found that exactly 8 vertices are individually removable, namely, the vertices indexed by 3, 4, 23, 24, 948, 949, 952, and 953 in our files. Furthermore, we found that removing all 8 of these vertices produces a 1577-vertex graph that is also not 4-colorable. As such, this graph appears to be the unique minimal 5-chromatic induced subgraph of the 1585-vertex graph above

G1577=IndexGraph@VertexDelete[G1585,{3,4,23,24,948,949,952,953}]

UnitDistanceGraphEmbeddingQ[G1577,WorkingPrecision->Infinity]//Quiet//Timing

VertexChromaticNumber[G1577]//Timing

GraphDataString

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

WriteString[file,GraphDataString[G1577,
"StandardName"->"MixonGraph1577",
"Name"->"Mixon graph 1577",
"Information"->"MixonGraph",
"ChromaticNumber"->5,
"Skip"->{"CliqueCoveringNumber","ConnectedInducedSubgraphPolynomial","CrossingNumber","DistinguishingNumber","DominatingSet","GracefulLabeling","GracefulLabelings","IndependencePolynomial","MatchingGeneratingPolynomial","MatchingPolynomial","MinimumDistinguishingLabelings","RadioNumber","TotalDominatingSet","VertexCover"},
TimeConstraint->5,
Debug->True]]

Close[file]

"MixonGraph1585"

Embeddings

All

GraphData["MixonGraph1585","Graph","All"]//StyleGraphs[#,VertexSize->{"Scaled",.01}]&

Circular

GraphData["MixonGraph1585","Graph","All"]//StyleGraphs[#,VertexSize->{"Scaled",.01}]&

LCF

GraphData["MixonGraph1585","LCF"]

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

Construction

https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/

https://asone.ai/polymath/index.php?title=Hadwiger-Nelson_problem

https://www.dropbox.com/s/x6kvu7b3wvdvqsn/graph.dimacs?dl=0

s=Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/UnitDistance/DeGrey/vertices_1585.sage","String"];

G1585Vertices=ToExpression["{"<>StringTake[#,{2,-2}]<>"}"]&/@StringSplit[StringReplace[StringTake[s,{2,-3}],ShortestMatch["sqrt("~~n__~~")"]:>"Sqrt["<>n<>"]"],",\n"]

Length[G1585Vertices]

ByteCount[G1585Vertices]

ByteCount[G1585VerticesSimplifed=FullSimplify[G1585Vertices]]//Timing

G1585=With[{v=G1585VerticesSimplifed},Graph[Range[Length[v]],UnitEdges[v],VertexCoordinates->v]]

e=ToExpression/@(StringSplit[StringDrop[#,2]]&/@Rest[Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/UnitDistance/DeGrey/graph.dimacs","Lines"]])

G1585=With[{v=G1585VerticesSimplifed},Graph[Range[Length[v]],UndirectedEdge@@@e,VertexCoordinates->v]]

EdgeCount[G1585]

UnitDistanceGraphEmbeddingQ[G1585,WorkingPrecision->Infinity]//Quiet//Timing

VertexChromaticNumber[G1585]//Timing

GraphDataString

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

WriteString[file,GraphDataString[G1585,
"StandardName"->"MixonGraph1585",
"Name"->"Mixon graph 1585",
"Information"->"MixonGraph",
"ChromaticNumber"->5,
"Skip"->{"CliqueCoveringNumber","ConnectedInducedSubgraphPolynomial","CrossingNumber","DistinguishingNumber","DominatingSet","GracefulLabeling","GracefulLabelings","IndependencePolynomial","MatchingGeneratingPolynomial","MatchingPolynomial","MinimumDistinguishingLabelings","RadioNumber","TotalDominatingSet","VertexCover"},
TimeConstraint->5,
Debug->True]]