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://ogarev-online.ru/2413-3639/article/view/347334
- ID: 347334
Cite item
Abstract
В настоящей работе доказано, что в каждом дистанционном графе на плоскости есть индуцированный подграф, содержащий более 91 процента вершин исходного графа и имеющий хроматическое число, не большее четырех. С помощью этого результата найден порядок роста пороговой вероятности для свойства случайного графа быть изоморфным некоторому дистанционному графу на плоскости. Предложены обобщения результатов на другие размерности.
About the authors
A. A. Kokotkin
Московский физико-технический институт141700, Московская область, г. Долгопрудный, Институтский переулок, 9
A. M. Raygorodskiy
Московский физико-технический институт141700, Московская область, г. Долгопрудный, Институтский переулок, 9
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.
Supplementary files
