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.
\Bibitem{Rai05}
\by A.~M.~Raigorodskii
\paper The Erd\H os--Hadwiger problem and the chromatic numbers of finite geometric graphs
\jour Sb. Math.
\yr 2005
\vol 196
\issue 1
\pages 115--146
\mathnet{http://mi.mathnet.ru/eng/sm1263}
\crossref{https://doi.org/10.1070/SM2005v196n01ABEH000874}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2141326}
\zmath{https://zbmath.org/?q=an:1070.05044}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000229078800005}
\elib{https://elibrary.ru/item.asp?id=9135669}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-18944367235}
Linking options:
https://www.mathnet.ru/eng/sm1263
https://doi.org/10.1070/SM2005v196n01ABEH000874
https://www.mathnet.ru/eng/sm/v196/i1/p123
This publication is cited in the following 25 articles:
A. M. Raigorodskii, T. V. Trukhan, “On the chromatic numbers of some distance graphs”, Dokl. Math., 98:2 (2018), 515–517
A. A. Sokolov, A. M. Raigorodskii, “O ratsionalnykh analogakh problem Nelsona–Khadvigera i Borsuka”, Chebyshevskii sb., 19:3 (2018), 270–281
L. E. Shabanov, “Turán type results for distance graphs in infinitesimal plane layer”, J. Math. Sci. (N. Y.), 236:5 (2019), 554–578
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
S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75
A. S. Gusev, “New Upper Bound for the Chromatic Numberof a Random Subgraph of a Distance Graph”, Math. Notes, 97:3 (2015), 326–332
V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Math. Notes, 97:6 (2015), 919–929
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
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
A. V. Burkin, “Small subgraphs in random distance graphs”, Theory Probab. Appl., 60:3 (2016), 367–382
Pyaderkin M.M., “on the Stability of the Erdos-Ko-Rado Theorem”, Dokl. Math., 91:3 (2015), 290–293
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
A. A. Kokotkin, “On Large Subgraphs of a Distance Graph Which Have Small Chromatic Number”, Math. Notes, 96:2 (2014), 298–300
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
Andrei M. Raigorodskii, Thirty Essays on Geometric Graph Theory, 2013, 429
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
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
A. M. Raigorodskii, “Around Borsuk's Hypothesis”, Journal of Mathematical Sciences, 154:4 (2008), 604–623
A. M. Raigorodskii, “Chromatic Numbers of Metric Spaces”, Journal of Mathematical Sciences, 154:4 (2008), 624–627
Citation in format AMSBIB
Contact us: