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/