Geodesic
Coloring Some Finite Sets in $ \mathbb{R}^n $
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 25-31.

Voir la notice de l'article provenant de la source Library of Science

This note relates to bounds on the chromatic number χ (ℝ^n) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝ^n so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs G_n in ℝ_n was introduced showing that χ(ℝ^n) ≥χ(G_n) ≥ (1+ o(1))n^2/6. For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that χ(G_n) ∼n^2/6 and find an exact formula for the chromatic number in the case of n = 2^k and n = 2^k − 1.
Keywords: chromatic number, independence number, distance graph 
@article{DMGT_2013_33_1_a2,
     author = {Balogh, J\'ozsef and Kostochka, Alexandr and Raigorodskii, Andrei},
     title = {Coloring {Some} {Finite} {Sets} in $ \mathbb{R}^n $},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {25--31},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a2/}
}
TY  - JOUR
AU  - Balogh, József
AU  - Kostochka, Alexandr
AU  - Raigorodskii, Andrei
TI  - Coloring Some Finite Sets in $ \mathbb{R}^n $
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 25
EP  - 31
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a2/
LA  - en
ID  - DMGT_2013_33_1_a2
ER  - 
%0 Journal Article
%A Balogh, József
%A Kostochka, Alexandr
%A Raigorodskii, Andrei
%T Coloring Some Finite Sets in $ \mathbb{R}^n $
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 25-31
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a2/
%G en
%F DMGT_2013_33_1_a2
Balogh, József; Kostochka, Alexandr; Raigorodskii, Andrei. Coloring Some Finite Sets in $ \mathbb{R}^n $. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 25-31. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a2/

[1] N.G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet. (A) 54 (1951) 371-373.

[2] P. Frankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981) 357-368. doi:10.1007/BF02579457

[3] A.B. Kupavskiy, On coloring spheres embedded into Rn, Sb. Math. 202(6) (2011) 83-110.

[4] A.B. Kupavskiy and A.M. Raigorodskii, On the chromatic number of R9, J. Math. Sci. 163(6) (2009) 720-731. doi:10.1007/s10958-009-9708-4

[5] D.G. Larman, A note on the realization of distances within sets in Euclidean space, Comment. Math. Helv. 53 (1978) 529-535. doi:10.1007/BF02566096

[6] D.G. Larman and C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972) 1-24. doi:10.1112/S0025579300004903

[7] N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory (A) 51 (1989) 24-42. doi:10.1016/0097-3165(89)90074-5

[8] A.M. Raigorodskii, On the chromatic number of a space, Russian Math. Surveys 55 (2000) N2, 351-352. doi:10.1070/RM2000v055n02ABEH000281

[9] A.M. Raigorodskii, The problems of Borsuk and Grünbaum on lattice polytopes, Izv. Math. 69(3) (2005) 81-108. English transl. Izv. Math. 69(3) (2005) 513-537. doi:10.1070/IM2005v069n03ABEH000537