General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Mat. Sb.:

Personal entry:
Save password
Forgotten password?

Mat. Sb., 2005, Volume 196, Number 1, Pages 123–156 (Mi msb1263)  

This article is cited in 21 scientific papers (total in 21 papers)

The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs

A. M. Raigorodskii

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: 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.


Full text: PDF file (519 kB)
References: PDF file   HTML file

English version:
Sbornik: Mathematics, 2005, 196:1, 115–146

Bibliographic databases:

UDC: 519.174 + 514.172.45
MSC: Primary 05C15, 52C10; Secondary 51M99
Received: 23.09.2003

Citation: A. M. Raigorodskii, “The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs”, Mat. Sb., 196:1 (2005), 123–156; Sb. Math., 196:1 (2005), 115–146

Citation in format AMSBIB
\by A.~M.~Raigorodskii
\paper The Erd\H os--Hadwiger problem and the chromatic numbers of finite geometric graphs
\jour Mat. Sb.
\yr 2005
\vol 196
\issue 1
\pages 123--156
\jour Sb. Math.
\yr 2005
\vol 196
\issue 1
\pages 115--146

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. M. Raigorodskii, “Colorings of spaces, and random graphs”, J. Math. Sci., 146:2 (2007), 5723–5730  mathnet  crossref  mathscinet  zmath  elib
    2. A. M. Raigorodskii, “On the Borsuk and Erdös–Hadwiger numbers”, Math. Notes, 79:6 (2006), 854–863  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    3. A. M. Raigorodskii, “Around Borsuk's Hypothesis”, Journal of Mathematical Sciences, 154:4 (2008), 604–623  mathnet  crossref  mathscinet  zmath  elib
    4. A. M. Raigorodskii, “Chromatic Numbers of Metric Spaces”, Journal of Mathematical Sciences, 154:4 (2008), 624–627  mathnet  crossref  mathscinet  zmath  elib
    5. N. G. Moshchevitin, A. M. Raigorodskii, “Colorings of the Space $\mathbb R^n$ with Several Forbidden Distances”, Math. Notes, 81:5 (2007), 656–664  mathnet  crossref  crossref  mathscinet  zmath  isi  elib  elib
    6. A. M. Raigorodskii, I. M. Shitova, “Chromatic numbers of real and rational spaces with real or rational forbidden distances”, Sb. Math., 199:4 (2008), 579–612  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    7. N. G. Moshchevitin, “Density modulo 1 of lacunary and sublacunary sequences: application of Peres–Schlag's construction”, J. Math. Sci., 180:5 (2012), 610–625  mathnet  crossref  mathscinet  elib
    8. A. B. Kupavskii, A. M. Raigorodskii, “Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii”, Sb. Math., 204:10 (2013), 1435–1479  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    9. A. A. Kokotkin, “On Large Subgraphs of a Distance Graph Which Have Small Chromatic Number”, Math. Notes, 96:2 (2014), 298–300  mathnet  crossref  mathscinet  zmath  isi  elib
    10. A. S. Gusev, “New Upper Bound for the Chromatic Numberof a Random Subgraph of a Distance Graph”, Math. Notes, 97:3 (2015), 326–332  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    11. V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Math. Notes, 97:6 (2015), 919–929  mathnet  crossref  crossref  mathscinet  isi  elib
    12. A. V. Bobu, O. A. Kostina, A. E. Kupriyanov, “Independence numbers and chromatic numbers of some distance graphs”, Problems Inform. Transmission, 51:2 (2015), 165–176  mathnet  crossref  isi  elib
    13. L. I. Bogolubsky, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Independence numbers and chromatic numbers of the random subgraphs of some distance graphs”, Sb. Math., 206:10 (2015), 1340–1374  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
    14. A. V. Burkin, “Small subgraphs in random distance graphs”, Theory Probab. Appl., 60:3 (2016), 367–382  mathnet  crossref  crossref  mathscinet  isi  elib
    15. Pyaderkin M.M., “on the Stability of the Erdos-Ko-Rado Theorem”, Dokl. Math., 91:3 (2015), 290–293  crossref  mathscinet  zmath  isi  elib
    16. A. V. Burkin, “The threshold probability for the property of planarity of a random subgraph of a regular graph”, Russian Math. Surveys, 70:6 (2015), 1170–1172  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    17. S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in $\mathbb Z^n$”, Sb. Math., 207:3 (2016), 458–478  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    18. S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75  mathnet  crossref  crossref  mathscinet  elib
    19. L. E. Shabanov, “Turán type results for distance graphs in infinitesimal plane layer”, J. Math. Sci. (N. Y.), 236:5 (2019), 554–578  mathnet  crossref
    20. A. M. Raigorodskii, T. V. Trukhan, “On the chromatic numbers of some distance graphs”, Dokl. Math., 98:2 (2018), 515–517  mathnet  crossref  crossref  zmath  isi  elib  scopus
    21. A. A. Sokolov, A. M. Raigorodskii, “O ratsionalnykh analogakh problem Nelsona–Khadvigera i Borsuka”, Chebyshevskii sb., 19:3 (2018), 270–281  mathnet  crossref  elib
  • Математический сборник - 1992–2005 Sbornik: Mathematics (from 1967)
    Number of views:
    This page:611
    Full text:216
    First page:1

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020