file:///C:/Users/Asger/OneDrive/Skrivebord/graph1.png

file:///C:/Users/Asger/OneDrive/Skrivebord/graph2.png

file:///C:/Users/Asger/OneDrive/Skrivebord/graph3.png

file:///C:/Users/Asger/OneDrive/Skrivebord/graphfinal.png

.

]]>This is the simplest unit-distance graph I could find that proves that the chromatic number of space is at least 6: (52 vertices and 166 edges) Does simpler graphs exist?

Consider first this 12 vertex graph:

Graph1:

Let A, Z and Æ be 3 same-colored vertices with the following coordinates:

A: (0, 0, 0)

Z: (sqrt(21/29), 13/sqrt(87), 0)

Æ: (-(15sqrt(87))/(48sqrt(7)+26sqrt(23)), (192sqrt(609)+59sqrt(2001))/(1152sqrt(7)+624sqrt(23)), (1/16)sqrt(51696sqrt(161)-655727))

Add the following 9 vertices:

B: (-(5sqrt(2001))/261, (40sqrt(87))/261, 0)

D: (0, sqrt(87)/6, 1/2)

E: (0, sqrt(87)/6, -1/2)

H: (sqrt(2001)/87, 13/(2sqrt(87)), 1/2)

I: (sqrt(2001)/87, 13/(2sqrt(87)), -1/2)

N: (-sqrt(23/87)/2+sqrt(3/58), (61+3sqrt(23/2))/(8sqrt(87)), (sqrt(23/2)-1)/8)

O: (-sqrt(23/87)/2-sqrt(3/58), (61-3sqrt(23/2))/(8sqrt(87)), -(1+sqrt(23/2))/8)

P: (-sqrt(23/87)/2-sqrt(3/58), (61-3sqrt(23/2))/(8sqrt(87)), (1+sqrt(23/2))/8)

Q: (-sqrt(23/87)/2+sqrt(3/58), (61+3sqrt(23/2))/(8sqrt(87)), (1-sqrt(23/2))/8)

We get 29 edges:

|ZD| = |ZE| = |ÆB| = |AH| = |AI| = |AN| = |AO| = |AP| = |AQ| = |BD| = |BE| = |BN| = |BO| = |BP| = |BQ|= |DE| = |DH| = |DP| = |DQ| = |EI| = |EN| = |EO| = |HI| = |HP| = |HQ| = |IN| = |IO| = |NO| = |PQ| = 1

This 12-vertex unit-distance graph can not be colored with less than 6 colors when A, Z and Æ have the same color. From this we can conclude that if a unit-distance graph contains a same-colored triangle with distances 2sqrt(2/3), 2sqrt(2/3) and sqrt(46)/4 then 9 vertices(and 29 edges) can be added to make sure you need at least 6 colors to color the graph.

Graph2:

Now, lets define the coordinates A, B, D, E, H, I, N, O, P and Q as before and define C and Ø like this:

C: ((5sqrt(2001))/261, (40sqrt(87))/261, 0)

Ø: (-(1517sqrt(2001))/120060, 5617/(480sqrt(87)), sqrt(11975617)/3680)

where

|CD|=|CE|=|BØ|=1

This 12-vertex unit-distance graph can not be colored with less than 6 colors when A, B and Ø have the same color. Conclusion: A triangle of same-colored vertices with the distances 5/3, 5/3 and (10sqrt(2001))/261 makes it possible to add 9 vertices(and 29 edges) so a unit-distance graph can be created that cannot be colored with less than 6 colors.

Graph3:

Finally we look at a 25 vertex graph. Define A, B, C, D, E, H, I, N, O, P and Q as before and add these 14 vertices:

F: (-sqrt(2001)/87, 13/(2sqrt(87)), 1/2)

G: (-sqrt(2001)/87, 13/(2sqrt(87)), -1/2)

J: (-sqrt(2001)/58, 163/(16sqrt(87)), 15/16)

K: (-sqrt(2001)/174, (35sqrt(87))/1392, 15/16)

L: (sqrt(2001)/58, 163/(16sqrt(87)), -15/16)

M: (sqrt(2001)/174, (35sqrt(87))/1392, -15/16)

R: (-(15sqrt(3/58)+7sqrt(23/87))/8, (419-(45sqrt(23/2)))/(64sqrt(87)), (15-sqrt(23/2))/64)

S: ((15sqrt(3/58)-7sqrt(23/87))/8, (419+45sqrt(23/2))/(64sqrt(87)), (15+sqrt(23/2))/64)

T: (sqrt(23/87)/2-sqrt(3/58), (61+3sqrt(23/2))/(8sqrt(87)), (1-sqrt(23/2))/8)

U: (sqrt(3/58)+sqrt(23/87)/2, (61-3sqrt(23/2))/(8sqrt(87)), (1+sqrt(23/2))/8)

V: (sqrt(3/58)+sqrt(23/87)/2, (61-3sqrt(23/2))/(8sqrt(87)), -(1+sqrt(23/2))/8)

W: (sqrt(23/87)/2-sqrt(3/58), (61+3sqrt(23/2))/(8sqrt(87)), (sqrt(23/2)-1)/8)

X: ((15sqrt(3/58)+7sqrt(23/87))/8, (419-45sqrt(23/2))/(64sqrt(87)), (sqrt(23/2)-15)/64)

Y: ((-15sqrt(3/58)+7sqrt(23/87))/8, (419+45sqrt(23/2))/(64sqrt(87)), -(15+sqrt(23/2))/64))

We get 79 edges:

|AH| = |AI| = |AN| = |AO| = |AP| = |AQ| = |BD| = |BE| = |BN| = |BO| = |BP| = |BQ|= |DE| = |DH| = |DP| = |DQ| = |EI| = |EN| = |EO| = |HI| = |HP| = |HQ| = |IN| = |IO| = |NO| = |PQ| = |CE| = |DE| = |CT| = |CU| = |CV| = |CW| = |DF| = |DT| = |DU| = |FG| = |AF| = |FT| = |FU| = |AT| = |AU| = |TU| = |EG| = |EV| = |EW| = |GV| = |GW| = |AG| = |AV| = |AW| = |VW| = |BJ| = |BR| = |BS| = |JD| = |JK| = |JR| = |JS| = |HK| = |AK| = |KR| = |KS| = |AR| = |AS| = |RS| = |CL| = |CX| = |CY| = |EL| = |LM| = |LX| = |LY| = |GM| = |AM| = |MX| = |MY| = |AX| = |AY| = |XY| = 1

A 4-coloring of this 25 vertex graph is impossible and a 5-coloring is only possible if we find a same-colored triangle in either A,B and C or in A,D and L or in A,E and J. Since these triangles are of the 2 types previously mentioned it is clear that we kan add 9×3 vertices to this 25 vertex graph and get a 52 vertex graph which requires at least 6 colors for a vertex coloring of the graph.

Can I post here?

]]>In any case, as far as upper estimates are concerned, nothing new has been invented for a long time, and such constructions are of interest. Do you plan to publish this?

]]>