178:, preserving all distances. Finite colorings of these spaces can be used to construct mappings from them to higher-dimensional spaces that preserve distances but are not isometries. For instance, the Euclidean plane can be mapped to a six-dimensional space by coloring it with seven colors so that no two points at distance one have the same color, and then mapping the points by their colors to the seven vertices of a six-dimensional
48:
36:
440:
One can also consider colorings of the plane in which the sets of points of each color are restricted to sets of some particular type. Such restrictions may cause the required number of colors to increase, as they prevent certain colorings from being considered acceptable. For instance, if a coloring
235:
are at unit distance from each other, we would not have a proper coloring of the unit distance graph of the plane. Therefore, at least four colors are needed to color this graph and the plane containing it. An alternative lower bound in the form of a ten-vertex four-chromatic unit distance graph, the
182:
with unit-length edges. This maps any two points at unit distance to distinct colors, and from there to distinct vertices of the simplex, at unit distance apart from each other. However, it maps all other distances to zero or one, so it is not an isometry. If the number of colors needed to color the
436:
is available using a generalization of the Moser spindle: a pair of the objects (each two simplexes glued together on a facet) which are joined on one side by a point and the other side by a line. An exponential lower bound was proved by Frankl and Wilson in 1981.
303:
The problem can easily be extended to higher dimensions. Finding the chromatic number of 3-space is a particularly interesting problem. As with the version on the plane, the answer is not known, but has been shown to be at least 6 and at most 15.
275:
to find non-4-colorable unit distance graphs with fewer vertices than the one in de Grey's construction. As of 2021, the smallest known unit distance graph with chromatic number 5 has 509 vertices. The page of the
Polymath project,
1140:
Functional-Analytic and
Complex Methods, their Interactions, and Applications to Partial Differential Equations: Proceedings of the International Workshop held at Graz University Of Technology, Graz, February 12–16,
158:
had earlier published a related result, showing that any cover of the plane by five congruent closed sets contains a unit distance in one of the sets, and he also mentioned the problem in a later paper
686:
356:
90:
at distance 1 from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 5, 6 or 7. The correct value may depend on the choice of axioms for
1138:
Rassias, Themistocles M. (2001), "Isometric mappings and the problem of A. D. Aleksandrov for conservative distances", in
Florian, H.; Ortner, N.; Schnitzer, F. J.; Tutschke, W. (eds.),
287:
of the plane by regular hexagons, with diameter slightly less than one, that can be assigned seven colors in a repeating pattern to form a 7-coloring of the plane. According to
191:
The fact that the chromatic number of the plane must be at least four follows from the existence of a seven-vertex unit distance graph with chromatic number four, named the
640:
408:
922:
434:
382:
127:
1327:
1099:
Radoičić, Radoš; Tóth, Géza (2003), "Note on the chromatic number of the space", in Aronov, Boris; Basu, Saugata; Pach, Janos; Sharir, Micha (eds.),
29:
215:
of these joined triangles are at unit distance from each other. If the plane could be three-colored, the coloring within the triangles would force
1085:
183:
plane could be reduced from seven to a lower number, the same reduction would apply to the dimension of the target space in this construction.
1292:
1211:
1156:
1121:
1042:
846:
174:, according to which any mapping of the Euclidean plane (or any higher dimensional space) to itself that preserves unit distances must be an
1055:
118:
and with an edge between two vertices if and only if the distance between the two points is 1. The
Hadwiger–Nelson problem is to find the
926:
1065:
830:
1332:
1222:
1347:
1201:
1260:
318:
171:
259:
posted discussion of de Grey's finding, with
Aaronson reporting independent verifications of de Grey's result using
678:
1342:
738:
1091:
1337:
311:-dimensional case of the problem, an easy upper bound on the number of required colorings found from tiling
698:
67:
251:
found a 1581-vertex, non-4-colourable unit-distance graph. The proof is computer assisted. Mathematician
115:
26:
How many colors are needed to color the plane so that no two points at unit distance are the same color?
1022:
953:
207:. Each of these triangles is joined along another edge to another equilateral triangle; the vertices
200:
1279:
719:
Chilakamarri, K. B. (1993), "The unit-distance graph problem: a brief survey and some new results",
703:
126:. As a consequence, the problem is often called "finding the chromatic number of the plane". By the
888:
111:
83:
60:
1310:
1012:
943:
905:
872:
763:
659:
454:
1207:
1152:
1117:
1081:
1038:
916:
842:
797:
241:
56:
1203:
The
Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators
1231:
1189:
1177:
1144:
1109:
897:
864:
818:
787:
747:
708:
649:
387:
272:
264:
138:) to that of finding the largest possible chromatic number of a finite unit distance graph.
119:
87:
1245:
1166:
1131:
965:
759:
671:
1241:
1162:
1127:
961:
755:
733:
667:
179:
135:
39:
A seven-coloring of the plane, and a four-chromatic unit distance graph in the plane (the
413:
361:
1302:
1037:, Wiley-Interscience Series in Discrete Mathematics and Optimization, pp. 150–152,
1026:
957:
736:(1996), "Unit-distance graphs, graphs on the integer lattice and a Ramsey type result",
1173:
901:
883:
834:
625:
292:
256:
248:
1193:
855:
Frankl, P.; Wilson, R.M. (1981), "Intersection theorems with geometric consequences",
822:
712:
247:
The lower bound was raised to five in 2018, when computer scientist and gerontologist
47:
1321:
1236:
988:
972:
767:
682:
192:
79:
75:
40:
43:), proving that the chromatic number of a plane is bounded above by 7 and below by 4
1143:, River Edge, New Jersey: World Scientific Publishing Co., Inc., pp. 118–125,
1004:
876:
442:
284:
237:
103:
52:
1108:, Algorithms and Combinatorics, vol. 25, Berlin: Springer, pp. 695–698,
934:
de Grey, Aubrey D.N.J. (2018), "The
Chromatic Number of the Plane Is at least 5",
1113:
283:
The upper bound of seven on the chromatic number follows from the existence of a
1275:
638:
Beckman, F. S.; Quarles, D. A. Jr. (1953), "On isometries of
Euclidean spaces",
268:
687:"A colour problem for infinite graphs and a problem in the theory of relations"
792:
775:
260:
91:
35:
801:
629:
150:, the problem was first formulated by Nelson in 1950, and first published by
1288:
1100:
1051:
252:
196:
886:(October 1960), "A new collection of 'brain-teasers'", Mathematical Games,
175:
1220:
Woodall, D. R. (1973), "Distances realized by sets covering the plane",
909:
975:(1945), "Überdeckung des euklidischen Raumes durch kongruente Mengen",
868:
809:
Coulson, D. (2002), "A 15-colouring of 3-space omitting distance one",
751:
663:
18:
1102:
Discrete and
Computational Geometry: The Goodman–Pollack Festschrift
654:
280:, contains further research, media citations and verification data.
1264:
1017:
948:
46:
1294:
Coloring
Problems for Arrangements of Circles (and Pseudocircles)
1148:
114:
of the plane: an infinite graph with all points of the plane as
1057:
Aubrey de Grey: The chromatic number of the plane is at least 5
82:, asks for the minimum number of colors required to color the
1180:(2003), "Axiom of choice and chromatic number of the plane",
1009:
Computing Small Unit-Distance Graphs with Chromatic Number 5
134:, the problem is equivalent (under the assumption of the
195:
after its discovery in 1961 by the brothers William and
416:
390:
364:
321:
271:, with Elkies and (separately) de Grey proposing a
167:discusses the problem and its history extensively.
428:
402:
376:
350:
170:One application of the problem connects it to the
1067:Polymath16, seventeenth thread: Declaring victory
351:{\displaystyle \lfloor 2+{\sqrt {n}}\rfloor ^{n}}
786:(2). Cambridge University Press (CUP): 191–196.
641:Proceedings of the American Mathematical Society
592:
1281:The chromatic number of the Unit Distance Graph
1087:Hadwiger-Nelson problem (Polymath project page)
780:Journal of the Australian Mathematical Society
631:Amazing progress on longstanding open problems
488:
131:
8:
579:
567:
476:
441:of the plane consists of regions bounded by
339:
322:
240:, was discovered at around the same time by
1265:"Problem 57: Chromatic Number of the Plane"
921:: CS1 maint: DOI inactive as of May 2024 (
776:"On the chromatic number of plane tilings"
611:for a different proof of a similar result.
147:
1235:
1182:Journal of Combinatorial Theory, Series A
1016:
947:
791:
702:
653:
445:, then at least six colors are required.
415:
389:
363:
342:
331:
320:
291:, this upper bound was first observed by
540:
277:
160:
155:
34:
1033:Jensen, Tommy R.; Toft, Bjarne (1995),
608:
604:
563:
524:
500:
465:
151:
30:(more unsolved problems in mathematics)
914:
512:
472:
288:
164:
991:(1961), "Ungelöste Probleme No. 40",
551:
536:
7:
691:Nederl. Akad. Wetensch. Proc. Ser. A
263:. Kalai linked additional posts by
1301:Grime, James (February 27, 2019),
1064:Mixon, Dustin (February 1, 2021),
902:10.1038/scientificamerican1060-218
358:. A lower bound from simplexes is
199:. This graph consists of two unit
14:
1328:Unsolved problems in graph theory
841:, Springer-Verlag, Problem G10,
593:Croft, Falconer & Guy (1991)
1313:from the original on 2021-12-21
1223:Journal of Combinatorial Theory
223:to both have the same color as
102:The question can be phrased in
21:Unsolved problem in mathematics
1:
1303:"A Colorful Unsolved Problem"
1194:10.1016/S0097-3165(03)00102-X
839:Unsolved Problems in Geometry
823:10.1016/S0012-365X(01)00183-2
713:10.1016/S1385-7258(51)50053-7
59:'s ten-vertex four-chromatic
1237:10.1016/0097-3165(73)90020-4
1114:10.1007/978-3-642-55566-4_32
925:) CS1 maint: date and year (
489:Beckman & Quarles (1953)
132:de Bruijn & Erdős (1951)
203:joined at a common vertex,
1364:
1200:Soifer, Alexander (2008),
580:Frankl & Wilson (1981)
568:Radoičić & Tóth (2003)
477:Shelah & Soifer (2003)
1269:The Open Problems Project
793:10.1017/s1446788700013574
98:Relation to finite graphs
739:Aequationes Mathematicae
732:Chilakamarri, Kiran B.;
721:Bull Inst. Combin. Appl.
148:Jensen & Toft (1995)
1035:Graph Coloring Problems
904:(inactive 2024-05-06),
255:and computer scientist
172:Beckman–Quarles theorem
128:de Bruijn–Erdős theorem
72:Hadwiger–Nelson problem
1333:Geometric graph theory
1206:, New York: Springer,
430:
404:
403:{\displaystyle n>1}
378:
352:
315:-dimensional cubes is
187:Lower and upper bounds
106:terms as follows. Let
68:geometric graph theory
63:
44:
1348:Mathematical problems
431:
405:
379:
353:
201:equilateral triangles
50:
38:
831:Falconer, Kenneth J.
774:Coulson, D. (2004).
414:
388:
362:
319:
16:Mathematical problem
1027:2018arXiv180512181H
958:2016arXiv160407134W
889:Scientific American
829:Croft, Hallard T.;
734:Mahoney, Carolyn R.
429:{\displaystyle n+2}
410:, a lower bound of
377:{\displaystyle n+1}
112:unit distance graph
61:unit distance graph
1082:Polymath, D. H. J.
1054:(April 10, 2018),
1005:Heule, Marijn J.H.
869:10.1007/BF02579457
752:10.1007/BF01831139
628:(April 11, 2018),
455:Four color theorem
426:
400:
374:
348:
227:, but then, since
64:
45:
1213:978-0-387-74640-1
1178:Soifer, Alexander
1158:978-981-02-4764-5
1123:978-3-540-00371-7
1044:978-0-471-02865-9
848:978-0-387-97506-1
336:
242:Solomon W. Golomb
86:such that no two
57:Solomon W. Golomb
1355:
1314:
1297:
1284:
1271:
1261:O'Rourke, Joseph
1248:
1239:
1216:
1196:
1169:
1134:
1107:
1095:
1090:, archived from
1077:
1076:
1074:
1060:
1047:
1029:
1020:
1000:
984:
968:
951:
930:
920:
912:
879:
851:
825:
805:
795:
770:
728:
715:
706:
679:de Bruijn, N. G.
674:
657:
634:
612:
602:
596:
589:
583:
577:
571:
561:
555:
549:
543:
534:
528:
522:
516:
510:
504:
498:
492:
486:
480:
470:
435:
433:
432:
427:
409:
407:
406:
401:
383:
381:
380:
375:
357:
355:
354:
349:
347:
346:
337:
332:
273:Polymath project
265:Jordan Ellenberg
120:chromatic number
22:
1363:
1362:
1358:
1357:
1356:
1354:
1353:
1352:
1343:Infinite graphs
1318:
1317:
1300:
1287:
1274:
1259:
1256:
1251:
1219:
1214:
1199:
1174:Shelah, Saharon
1172:
1159:
1137:
1124:
1105:
1098:
1080:
1072:
1070:
1063:
1050:
1045:
1032:
1003:
987:
977:Portugal. Math.
971:
933:
913:
884:Gardner, Martin
882:
854:
849:
835:Guy, Richard K.
828:
808:
773:
731:
718:
704:10.1.1.210.6623
677:
655:10.2307/2032415
637:
626:Aaronson, Scott
624:
620:
615:
603:
599:
590:
586:
578:
574:
562:
558:
550:
546:
541:Aaronson (2018)
535:
531:
523:
519:
511:
507:
499:
495:
487:
483:
475:, pp. 557–563;
471:
467:
463:
451:
412:
411:
386:
385:
360:
359:
338:
317:
316:
301:
278:Polymath (2018)
189:
180:regular simplex
156:Hadwiger (1945)
144:
136:axiom of choice
104:graph theoretic
100:
33:
32:
27:
24:
20:
17:
12:
11:
5:
1361:
1359:
1351:
1350:
1345:
1340:
1338:Graph coloring
1335:
1330:
1320:
1319:
1316:
1315:
1298:
1285:
1272:
1255:
1254:External links
1252:
1250:
1249:
1230:(2): 187–200,
1217:
1212:
1197:
1188:(2): 387–391,
1170:
1157:
1135:
1122:
1096:
1084:(April 2018),
1078:
1061:
1048:
1043:
1030:
1001:
989:Hadwiger, Hugo
985:
973:Hadwiger, Hugo
969:
936:Geombinatorics
931:
880:
863:(4): 357–368,
852:
847:
826:
817:(1–2): 83–90,
811:Discrete Math.
806:
771:
746:(1–2): 48–67,
729:
716:
675:
648:(5): 810–815,
635:
621:
619:
616:
614:
613:
609:Coulson (2004)
605:Woodall (1973)
597:
584:
572:
564:Coulson (2002)
556:
544:
529:
525:de Grey (2018)
517:
505:
501:Rassias (2001)
493:
481:
464:
462:
459:
458:
457:
450:
447:
425:
422:
419:
399:
396:
393:
373:
370:
367:
345:
341:
335:
330:
327:
324:
300:
297:
293:John R. Isbell
257:Scott Aaronson
249:Aubrey de Grey
188:
185:
152:Gardner (1960)
143:
140:
130:, a result of
99:
96:
74:, named after
28:
25:
19:
15:
13:
10:
9:
6:
4:
3:
2:
1360:
1349:
1346:
1344:
1341:
1339:
1336:
1334:
1331:
1329:
1326:
1325:
1323:
1312:
1308:
1304:
1299:
1296:
1295:
1290:
1286:
1283:
1282:
1277:
1273:
1270:
1266:
1262:
1258:
1257:
1253:
1247:
1243:
1238:
1233:
1229:
1225:
1224:
1218:
1215:
1209:
1205:
1204:
1198:
1195:
1191:
1187:
1183:
1179:
1175:
1171:
1168:
1164:
1160:
1154:
1150:
1146:
1142:
1136:
1133:
1129:
1125:
1119:
1115:
1111:
1104:
1103:
1097:
1094:on 2022-02-16
1093:
1089:
1088:
1083:
1079:
1069:
1068:
1062:
1059:
1058:
1053:
1049:
1046:
1040:
1036:
1031:
1028:
1024:
1019:
1014:
1010:
1006:
1002:
998:
994:
990:
986:
982:
978:
974:
970:
967:
963:
959:
955:
950:
945:
941:
937:
932:
928:
924:
918:
911:
907:
903:
899:
895:
891:
890:
885:
881:
878:
874:
870:
866:
862:
858:
857:Combinatorica
853:
850:
844:
840:
836:
832:
827:
824:
820:
816:
812:
807:
803:
799:
794:
789:
785:
781:
777:
772:
769:
765:
761:
757:
753:
749:
745:
741:
740:
735:
730:
726:
722:
717:
714:
710:
705:
700:
696:
692:
688:
684:
680:
676:
673:
669:
665:
661:
656:
651:
647:
643:
642:
636:
633:
632:
627:
623:
622:
617:
610:
606:
601:
598:
594:
588:
585:
581:
576:
573:
569:
565:
560:
557:
553:
548:
545:
542:
538:
533:
530:
526:
521:
518:
515:, p. 19.
514:
513:Soifer (2008)
509:
506:
502:
497:
494:
490:
485:
482:
478:
474:
473:Soifer (2008)
469:
466:
460:
456:
453:
452:
448:
446:
444:
443:Jordan curves
438:
423:
420:
417:
397:
394:
391:
371:
368:
365:
343:
333:
328:
325:
314:
310:
305:
298:
296:
294:
290:
289:Soifer (2008)
286:
281:
279:
274:
270:
266:
262:
258:
254:
250:
245:
243:
239:
234:
230:
226:
222:
218:
214:
210:
206:
202:
198:
194:
193:Moser spindle
186:
184:
181:
177:
173:
168:
166:
165:Soifer (2008)
162:
161:Hadwiger 1961
157:
153:
149:
146:According to
141:
139:
137:
133:
129:
125:
121:
117:
113:
109:
105:
97:
95:
93:
89:
85:
81:
80:Edward Nelson
77:
76:Hugo Hadwiger
73:
69:
62:
58:
54:
49:
42:
41:Moser spindle
37:
31:
1306:
1293:
1280:
1276:Mohar, Bojan
1268:
1227:
1226:, Series A,
1221:
1202:
1185:
1181:
1149:10.1142/4822
1139:
1101:
1092:the original
1086:
1071:, retrieved
1066:
1056:
1034:
1008:
996:
992:
980:
976:
939:
935:
893:
887:
860:
856:
838:
814:
810:
783:
779:
743:
737:
724:
720:
694:
690:
645:
639:
630:
600:
587:
575:
559:
552:Mixon (2021)
547:
537:Kalai (2018)
532:
520:
508:
496:
484:
468:
439:
312:
308:
306:
302:
285:tessellation
282:
246:
238:Golomb graph
232:
228:
224:
220:
216:
212:
208:
204:
190:
169:
145:
123:
107:
101:
71:
65:
53:Golomb graph
1307:Numberphile
993:Elem. Math.
697:: 371–373,
607:; see also
591:See, e.g.,
269:Noam Elkies
261:SAT solvers
1322:Categories
1289:Kalai, Gil
1052:Kalai, Gil
1018:1805.12181
949:1804.02385
896:(4): 180,
618:References
299:Variations
92:set theory
1073:16 August
999:: 103–104
983:: 238–242
802:1446-7887
768:189831504
699:CiteSeerX
683:Erdős, P.
340:⌋
323:⌊
253:Gil Kalai
197:Leo Moser
1311:archived
1291:(2018),
1278:(2001),
1007:(2018),
942:: 5–18,
917:citation
910:24940666
837:(1991),
685:(1951),
449:See also
176:isometry
116:vertices
1246:0310770
1167:1893253
1132:2038498
1023:Bibcode
966:3820926
954:Bibcode
877:6768348
760:1372782
727:: 39–60
672:0058193
664:2032415
307:In the
142:History
110:be the
1244:
1210:
1165:
1155:
1130:
1120:
1041:
964:
908:
875:
845:
800:
766:
758:
701:
670:
662:
384:. For
88:points
70:, the
1106:(PDF)
1013:arXiv
944:arXiv
906:JSTOR
873:S2CID
764:S2CID
660:JSTOR
461:Notes
84:plane
1208:ISBN
1153:ISBN
1141:2001
1118:ISBN
1075:2021
1039:ISBN
927:link
923:link
843:ISBN
798:ISSN
395:>
267:and
231:and
219:and
211:and
78:and
51:The
1232:doi
1190:doi
1186:103
1145:doi
1110:doi
898:doi
894:203
865:doi
819:doi
815:256
788:doi
748:doi
709:doi
650:doi
163:).
122:of
66:In
1324::
1309:,
1305:,
1267:,
1263:,
1242:MR
1240:,
1228:14
1184:,
1176:;
1163:MR
1161:,
1151:,
1128:MR
1126:,
1116:,
1021:,
1011:,
997:16
995:,
979:,
962:MR
960:,
952:,
940:28
938:,
919:}}
915:{{
892:,
871:,
859:,
833:;
813:,
796:.
784:77
782:.
778:.
762:,
756:MR
754:,
744:51
742:,
723:,
707:,
695:54
693:,
689:,
681:;
668:MR
666:,
658:,
644:,
566:;
539:;
295:.
244:.
154:.
94:.
55:,
1234::
1192::
1147::
1112::
1025::
1015::
981:4
956::
946::
929:)
900::
867::
861:1
821::
804:.
790::
750::
725:8
711::
652::
646:4
595:.
582:.
570:.
554:.
527:.
503:.
491:.
479:.
424:2
421:+
418:n
398:1
392:n
372:1
369:+
366:n
344:n
334:n
329:+
326:2
313:n
309:n
233:z
229:y
225:x
221:z
217:y
213:z
209:y
205:x
159:(
124:G
108:G
23::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
