On Large Subgraphs with Small Chromatic Numbers Contained in Distance Graphs
- Авторлар: Kokotkin A.1, Raigorodskii A.1
-
Мекемелер:
- Moscow Institute of Physics and Technology
- Шығарылым: Том 214, № 5 (2016)
- Беттер: 665-674
- Бөлім: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/237485
- DOI: https://doi.org/10.1007/s10958-016-2804-3
- ID: 237485
Дәйексөз келтіру
Аннотация
It is proved that each distance graph on a plane has an induced subgraph with a chromatic number that is at most 4 containing over 91% of the vertices of the original graph. This result is used to obtain the asymptotic growth rate for a threshold probability that a random graph is isomorphic to a certain distance graph on a plane. Several generalizations to larger dimensions are proposed.
Негізгі сөздер
Авторлар туралы
A. Kokotkin
Moscow Institute of Physics and Technology
Хат алмасуға жауапты Автор.
Email: kokocan@yandex.ru
Ресей, Moscow
A. Raigorodskii
Moscow Institute of Physics and Technology
Хат алмасуға жауапты Автор.
Email: mraigor@yandex.ru
Ресей, Moscow