O bol'shikh podgrafakh grafa rasstoyaniy, imeyushchikh malen'koe khromaticheskoe chislo

Cover Page

Cite item

Full Text

Abstract

В настоящей работе доказано, что в каждом дистанционном графе на плоскости есть индуцированный подграф, содержащий более 91 процента вершин исходного графа и имеющий хроматическое число, не большее четырех. С помощью этого результата найден порядок роста пороговой вероятности для свойства случайного графа быть изоморфным некоторому дистанционному графу на плоскости. Предложены обобщения результатов на другие размерности.

About the authors

A. A. Kokotkin

A. M. Raygorodskiy

References

  1. Колчин В. Ф. Случайные графы. - М.: Физматлит, 2002.
  2. Купавский А. Б., Райгородский А. М., Титова М. В. О плотнейших множествах без расстояния единица в пространствах малых размерностей// Тр. МФТИ. - 4, № 1. - 2012. - С. 91-110.
  3. Райгородский А. М. Проблема Борсука и хроматические числа метрических пространств// Усп. мат. наук. - 2001. - 56, № 1. - С. 107-146.
  4. Райгородский А. М. О хроматическом числе пространства// Усп. мат. наук. - 2000. - 55, № 2. - С. 147-148.
  5. Райгородский А. М. Хроматические числа. - М.: МЦНМО, 2003.
  6. Райгородский А. М. Линейно-алгебраический метод в комбинаторике. - М.: МЦНМО, 2007.
  7. Райгородский А. М. Модели случайных графов. - М.: МЦНМО, 2011.
  8. Сойфер А. Хроматическое число плоскости: его прошлое, настоящее и будущее// Мат. просвещ. - 2004. - 8.
  9. Agarwal P. K., Pach J. Combinatorial geometry. - New York: John Wiley and Sons Inc., 1995.
  10. Alon N., Spencer J. The probabilistic method. - Wiley-Interscience Ser. Discr. Math. Optim., 2000.
  11. Bolloba´ s B. Random graphs. - Cambridge Univ. Press, 2001.
  12. Brass P., Moser W., Pach J. Research problems in discrete geometry. - Springer, 2005.
  13. Coulson D. A 15-colouring of 3-space omitting distance one// Discrete Math. - 2002. - 256. - С. 83-90.
  14. Croft H. T. Incident incidents// Eureka (Cambridge). - 1967. - 30. - С. 22-26.
  15. 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.
  16. Janson S., Luczak T., Rucin´ ski A. Random graphs. - New York: Wiley, 2000.
  17. Klee V., Wagon S. Old and new unsolved problems in plane geometry and number theory. - Math. Association of America, 1991.
  18. Larman D. G., Rogers C. A. The realization of distances within sets in Euclidean space// Mathematika. - 1972. - 19. - С. 1-24.
  19. Nechushtan O. Note on the space chromatic number// Discrete Math. - 2002. - 256. - С. 499-507.
  20. Soifer A. The mathematical coloring book. - Springer, 2009.
  21. 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.

Copyright (c) 2013 Kokotkin A.A., Raygorodskiy A.M.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies