Geodesic
The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs
Sbornik. Mathematics, Tome 196 (2005) no. 1, pp. 115-146 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This paper is devoted to the classical Erdős–Hadwiger problem in combinatorial geometry. This problem of finding the minimum number of colours sufficient for colouring all points in the Euclidean space $\mathbb R^n$ such that points lying at distance 1 are painted distinct colours, is studied in one of the most important special cases relating to colouring of finite geometric graphs. Several new approaches to lower bounds for the chromatic numbers of such graphs are put forward. In a very broad class of cases these approaches enable one to obtain a considerable improvement over and generalization of all previously known results of this kind. 
@article{SM_2005_196_1_a4,
     author = {A. M. Raigorodskii},
     title = {The {Erd\H{o}s{\textendash}Hadwiger} problem and the chromatic numbers of finite geometric graphs},
     journal = {Sbornik. Mathematics},
     pages = {115--146},
     year = {2005},
     volume = {196},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2005_196_1_a4/}
}
TY  - JOUR
AU  - A. M. Raigorodskii
TI  - The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs
JO  - Sbornik. Mathematics
PY  - 2005
SP  - 115
EP  - 146
VL  - 196
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SM_2005_196_1_a4/
LA  - en
ID  - SM_2005_196_1_a4
ER  - 
%0 Journal Article
%A A. M. Raigorodskii
%T The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs
%J Sbornik. Mathematics
%D 2005
%P 115-146
%V 196
%N 1
%U http://geodesic.mathdoc.fr/item/SM_2005_196_1_a4/
%G en
%F SM_2005_196_1_a4
A. M. Raigorodskii. The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs. Sbornik. Mathematics, Tome 196 (2005) no. 1, pp. 115-146. http://geodesic.mathdoc.fr/item/SM_2005_196_1_a4/

[1] Hadwiger H., “Ein Überdeckungssatz für den Euklidischen Raum”, Portugal. Math., 4 (1944), 140–144 | MR | Zbl

[2] Kharari F., Teoriya grafov, Mir, M., 1973 | MR

[3] Distel R., Teoriya grafov, Izd-vo In-ta matematiki, Novosibirsk, 2002

[4] Klee V., Wagon S., Old and new unsolved problems in plane geometry and number theory, Math. Association of America, Washington, 1991 | MR

[5] Székely L. A., “Erdös on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his mathematics, Bolyai Soc. Math. Stud., 11, Springer, Berlin, 2002, 649–666 | MR | Zbl

[6] Raigorodskii A. M., “Problema Borsuka i khromaticheskie chisla metricheskikh prostranstv”, UMN, 56:1 (2001), 107–146 | MR | Zbl

[7] Raiskii D. E., “Realizatsiya vsekh rasstoyanii pri razbienii prostranstva $\mathbb R^n$ na $n+1$ chast”, Matem. zametki, 7 (1970), 319–323 | MR

[8] Larman D. G., Rogers C. A., “The realization of distances within sets in Euclidean space”, Matematika, 19 (1972), 1–24 | MR | Zbl

[9] Larman D. G., “A note on the realization of distances within sets in Euclidean space”, Comment. Math. Helv., 53 (1978), 529–535 | DOI | MR | Zbl

[10] Frankl P., Wilson R., “Intersection theorems with geometric consequences”, Combinatorica, 1 (1981), 357–368 | DOI | MR | Zbl

[11] Raigorodskii A. M., “O khromaticheskom chisle prostranstva”, UMN, 55:2 (2000), 147–148 | MR | Zbl

[12] de Bruijn N. G., Erdös P., “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Acad. Wet., Proc., Ser. A, 54:5 (1951), 371–373 | Zbl

[13] Raigorodskii A. M., “Ob odnoi otsenke v probleme Borsuka”, UMN, 54:2 (1999), 185–186 | MR | Zbl

[14] Raigorodskii A. M., “Zadachi Borsuka i Khadvigera i sistemy vektorov s zapretami na skalyarnye proizvedeniya”, UMN, 57:3 (2002), 159–160 | MR

[15] Raigorodskii A. M., “The Borsuk partition problem: the seventieth anniversary”, Math. Intell., 26:3 (2004), 4–12 | DOI | MR | Zbl

[16] Raigorodskii A. M., “Problema Borsuka dlya $(0,1)$-mnogogrannikov i kross-politopov”, Dokl. RAN, 371:5 (2000), 600–603 | MR

[17] Raigorodskii A. M., “Problema Borsuka dlya $(0,1)$-mnogogrannikov i kross-politopov”, Dokl. RAN, 384:5 (2002), 593–597 | MR | Zbl

[18] Raigorodskii A. M., “Problemy Borsuka, Khadvigera i Gryunbauma dlya nekotorykh klassov mnogogrannikov i grafov”, Dokl. RAN, 388:6 (2003), 738–742 | MR | Zbl

[19] Ziegler G. M., “Lectures on $0/1$-polytopes”, Polytopes – combinatorics and computation, DMV Sem., 29, eds. G. Kalai et al., Birkhäuser, Basel, 2000, 1–44 | MR

[20] Ziegler G. M., “Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions”, Lecture Notes in Comput. Sci., 2122, 2001, 159–171 | MR | Zbl

[21] Payan C., “On the chromatic number of cube-like graphs”, Discrete Math., 103 (1992), 271–277 | DOI | MR | Zbl

[22] Schiller F., “Zur Berechnung und Abschätzung von Färbungszahlen und der $\vartheta$-Funktion von Graphen”, Diplomarbeit, Technische Universitat, Berlin, 1999 | Zbl

[23] Linial N., Meshulam R., Tarsi M., “Matroidal bijections between graphs”, J. Combin. Theory Ser. B, 45:1 (1988), 31–44 | DOI | MR | Zbl

[24] Prakhar K., Raspredelenie prostykh chisel, Mir, M., 1967 | MR

[25] Bollobás B., Random graphs, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[26] Bollobás B., “The chromatic number of random graphs”, Combinatorica, 8 (1988), 49–56 | DOI | MR

[27] Alon N., Spencer J., The probabilistic method, Wiley, Chichester, 2000 | MR

[28] Babai L., Frankl P., Linear algebra methods in combinatorics, Part 1, The University of Chicago, Chicago, 1992 | Zbl

[29] Alon N., Babai L., Suzuki H., “Multilinear polynomials and Frankl–Ray–Chaudhuri–Wilson type intersection theorems”, J. Combin. Theory. Ser. A, 58 (1991), 165–180 | DOI | MR | Zbl

[30] Hadwiger H., “Ungelöste Probleme No 40”, Elem. Math., 16 (1961), 103–104 | MR

[31] Moser L., Moser W., “Solution to problem 10”, Canad. Math. Bull., 4 (1961), 187–189