This article is cited in 1 paper

On large subgraphs with small chromatic numbers contained in distance graphs

A. A. Kokotkin, A. M. Raigorodskii

Dolgoprudnyi, Moscow region, Russia

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.

UDC: 519.174

 English version: Journal of Mathematical Sciences, 2016, 214:5, 665–674