# Coloring Some Finite Sets in ℝn

József Balogh; Alexandr Kostochka; Andrei Raigorodskii

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 1, page 25-31
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJózsef Balogh, Alexandr Kostochka, and Andrei Raigorodskii. "Coloring Some Finite Sets in ℝn." Discussiones Mathematicae Graph Theory 33.1 (2013): 25-31. <http://eudml.org/doc/267832>.

@article{JózsefBalogh2013,

abstract = {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 Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of n = 2k and n = 2k − 1.},

author = {József Balogh, Alexandr Kostochka, Andrei Raigorodskii},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {chromatic number; independence number; distance graph},

language = {eng},

number = {1},

pages = {25-31},

title = {Coloring Some Finite Sets in ℝn},

url = {http://eudml.org/doc/267832},

volume = {33},

year = {2013},

}

TY - JOUR

AU - József Balogh

AU - Alexandr Kostochka

AU - Andrei Raigorodskii

TI - Coloring Some Finite Sets in ℝn

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 1

SP - 25

EP - 31

AB - 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 Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of n = 2k and n = 2k − 1.

LA - eng

KW - chromatic number; independence number; distance graph

UR - http://eudml.org/doc/267832

ER -

## References

top- [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. Zbl0044.38203
- [2] P. Frankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981) 357-368. doi:10.1007/BF02579457[Crossref] Zbl0498.05048
- [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[Crossref] Zbl1288.05093
- [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[Crossref]
- [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[Crossref] Zbl0246.05020
- [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[Crossref] Zbl0729.05038
- [8] A.M. Raigorodskii, On the chromatic number of a space, Russian Math. Surveys 55 (2000) N2, 351-352. doi:10.1070/RM2000v055n02ABEH000281[Crossref]
- [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[Crossref]

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.