Enviar artigo por via de e-mail On Large Subgraphs with Small Chromatic Numbers Contained in Distance Graphs
- Autores: Kokotkin A.1, Raigorodskii A.1
-
Afiliações:
- Moscow Institute of Physics and Technology
- Edição: Volume 214, Nº 5 (2016)
- Páginas: 665-674
- Seção: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/237485
- DOI: https://doi.org/10.1007/s10958-016-2804-3
- ID: 237485
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Palavras-chave
Sobre autores
A. Kokotkin
Moscow Institute of Physics and Technology
Autor responsável pela correspondência
Email: kokocan@yandex.ru
Rússia, Moscow
A. Raigorodskii
Moscow Institute of Physics and Technology
Autor responsável pela correspondência
Email: mraigor@yandex.ru
Rússia, Moscow
