O bol'shikh podgrafakh grafa rasstoyaniy, imeyushchikh malen'koe khromaticheskoe chislo
- Authors: Kokotkin A.A.1, Raygorodskiy A.M.1
-
Affiliations:
- Issue: Vol 51, No (2013)
- Pages: 64-73
- Section: Articles
- URL: https://journals.rudn.ru/CMFD/article/view/33538
Cite item
Full Text
Abstract
В настоящей работе доказано, что в каждом дистанционном графе на плоскости есть индуцированный подграф, содержащий более 91 процента вершин исходного графа и имеющий хроматическое число, не большее четырех. С помощью этого результата найден порядок роста пороговой вероятности для свойства случайного графа быть изоморфным некоторому дистанционному графу на плоскости. Предложены обобщения результатов на другие размерности.
References
- Колчин В. Ф. Случайные графы. - М.: Физматлит, 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.
