Hadwiger-Nelson Problem
Author
Eric W. Weisstein
Title
Hadwiger-Nelson Problem
Description
The Hadwiger-Nelson problem asks for the chromatic number of the plane, i.e., the minimum number of colors needed to color the plane if no two points at unit distance one from one another are given the same color. The problem was first discussed (though not published) by Nelson in 1950 (Soifer 2008, de Grey 2018). Since that time, the exact answer was known to be 4, 5, 6, or 7, with the lower bound provided by unit-distance graphs such as the Moser spindle and Golomb graph (both of which...
Category
Educational Materials
Keywords
URL
http://www.notebookarchive.org/2019-07-0z3zbt6/
DOI
https://notebookarchive.org/2019-07-0z3zbt6
Date Added
2019-07-02
Date Last Modified
2019-07-02
File Size
254.48 kilobytes
Supplements
Rights
Redistribution rights reserved
Hadwiger-Nelson Problem
Hadwiger-Nelson Problem
Author
Author
Eric W. Weisstein
May 7, 2018
May 7, 2018
This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Hadwiger-NelsonProblem.nb.
For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Hadwiger-NelsonProblem.html.
©2018 Wolfram Research, Inc. except for portions noted otherwise
Unit-distance graphs sorted by chromatic number
Unit-distance graphs sorted by chromatic number
Triangle-free
Triangle-free
In[]:=
TextGrid[Function[g,{g[[1,1]],TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[Sort[GraphData[#,{"V","#"}]&/@g[[All,2]]],First]]}]/@SplitBy[Sort[GraphData[#,{"ChromaticNumber","#"}]&/@GraphData[{"TriangleFree","UnitDistance"}]],First],DividersAll,AlignmentLeft]
Out[]=
All
All
In[]:=
TextGrid[Function[g,{g[[1,1]],TextGrid[{#[[1,1]],#[[All,2]]}&/@SplitBy[Sort[GraphData[#,{"V","#"}]&/@g[[All,2]]],First]]}]/@SplitBy[Sort[GraphData[#,{"ChromaticNumber","#"}]&/@GraphData["UnitDistance"]],First],DividersAll,AlignmentLeft]
Out[]=
Cite this as: Eric W. Weisstein, "Hadwiger-Nelson Problem" from the Notebook Archive (2018), https://notebookarchive.org/2019-07-0z3zbt6