Email this article On Large Subgraphs with Small Chromatic Numbers Contained in Distance Graphs
- Authors: Kokotkin A.1, Raigorodskii A.1
-
Affiliations:
- Moscow Institute of Physics and Technology
- Issue: Vol 214, No 5 (2016)
- Pages: 665-674
- Section: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/237485
- DOI: https://doi.org/10.1007/s10958-016-2804-3
- ID: 237485
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
A. Kokotkin
Moscow Institute of Physics and Technology
Author for correspondence.
Email: kokocan@yandex.ru
Russian Federation, Moscow
A. Raigorodskii
Moscow Institute of Physics and Technology
Author for correspondence.
Email: mraigor@yandex.ru
Russian Federation, Moscow
