Contemporary Mathematics. Fundamental DirectionsContemporary Mathematics. Fundamental DirectionsСовременная математика. Фундаментальные направления2413-36392949-0618Peoples’ Friendship University of Russia named after Patrice Lumumba (RUDN University)33538ArticlesСтатьиResearch ArticleO bol'shikh podgrafakh grafa rasstoyaniy, imeyushchikh malen'koe khromaticheskoe chisloО больших подграфах графа расстояний, имеющих маленькое хроматическое числоKokotkinA. A.КокоткинА. А.-RaygorodskiyA. M.РайгородскийА. М.-Московский физико-технический институт1512201351VOL 51, NO (2013)ТОМ 51, № (2013)647310022023Copyright ©; 2013, Kokotkin A.A., Raygorodskiy A.M.Copyright ©; 2013, Кокоткин А.А., Райгородский А.М.2013Kokotkin A.A., Raygorodskiy A.M.Кокоткин А.А., Райгородский А.М.https://creativecommons.org/licenses/by-nc/4.0https://journals.rudn.ru/CMFD/article/view/33538В настоящей работе доказано, что в каждом дистанционном графе на плоскости есть индуцированный подграф, содержащий более 91 процента вершин исходного графа и имеющий хроматическое число, не большее четырех. С помощью этого результата найден порядок роста пороговой вероятности для свойства случайного графа быть изоморфным некоторому дистанционному графу на плоскости. Предложены обобщения результатов на другие размерности.[Колчин В. Ф. Случайные графы. - М.: Физматлит, 2002.][Купавский А. Б., Райгородский А. М., Титова М. В. О плотнейших множествах без расстояния единица в пространствах малых размерностей// Тр. МФТИ. - 4, № 1. - 2012. - С. 91-110.][Райгородский А. М. Проблема Борсука и хроматические числа метрических пространств// Усп. мат. наук. - 2001. - 56, № 1. - С. 107-146.][Райгородский А. М. О хроматическом числе пространства// Усп. мат. наук. - 2000. - 55, № 2. - С. 147-148.][Райгородский А. М. Хроматические числа. - М.: МЦНМО, 2003.][Райгородский А. М. Линейно-алгебраический метод в комбинаторике. - М.: МЦНМО, 2007.][Райгородский А. М. Модели случайных графов. - М.: МЦНМО, 2011.][Сойфер А. Хроматическое число плоскости: его прошлое, настоящее и будущее// Мат. просвещ. - 2004. - 8.][Agarwal P. K., Pach J. Combinatorial geometry. - New York: John Wiley and Sons Inc., 1995.][Alon N., Spencer J. The probabilistic method. - Wiley-Interscience Ser. Discr. Math. Optim., 2000.][Bolloba´ s B. Random graphs. - Cambridge Univ. Press, 2001.][Brass P., Moser W., Pach J. Research problems in discrete geometry. - Springer, 2005.][Coulson D. A 15-colouring of 3-space omitting distance one// Discrete Math. - 2002. - 256. - С. 83-90.][Croft H. T. Incident incidents// Eureka (Cambridge). - 1967. - 30. - С. 22-26.][De Bruijn N. G., Erdo˝s P. A colour problem for in nite graphs and a problem in the theory of relations// Proc. Koninkl. Nederl. Acad. Wet. Ser. A. - 54, № 5. - 1951. - С. 371-373.][Janson S., Luczak T., Rucin´ ski A. Random graphs. - New York: Wiley, 2000.][Klee V., Wagon S. Old and new unsolved problems in plane geometry and number theory. - Math. Association of America, 1991.][Larman D. G., Rogers C. A. The realization of distances within sets in Euclidean space// Mathematika. - 1972. - 19. - С. 1-24.][Nechushtan O. Note on the space chromatic number// Discrete Math. - 2002. - 256. - С. 499-507.][Soifer A. The mathematical coloring book. - Springer, 2009.][Sze´kely L. A., Erdo˝s P. On unit distances and the Szemere´di-Trotter theorems// Paul Erdo˝s and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11. - 2002. - С. 649-666.]