On large subgraphs of a distance graph which have small chromatic number (Q2342369)

In the paper, some results on distance graphs in two-dimensional Euclidean space are presented without proofs. Vertices in a distance graph correspond to points in the plane, and two vertices are adjacent if their Euclidean distance is equal to \(1\). The chromatic number of the plane is defined as a maximum of chromatic numbers of distance graphs realized in the plane. The first result estimates the number of vertices in an induced subgraph \(G'\) with chromatic number \(\chi (G')=k\) of any distance graph \(G\) on \(n\) vertices in the plane. In the next two results, the author presents estimations of the threshold probability for the realization of a random graph \(G(n,p)\) as a distance graph in the plane. \[ \frac{1-\epsilon}{n} \leq p^*(n) \leq \frac{t_0 +\epsilon}{n} \] where \(t_0 = 14.797\). The threshold probability \(p^* (n)\) is defined as \[ p^* (n) = \sup\{ p\in [0,1] : P_n (G\text{ can be realized as a distance graph in the plane})>1/2\} \]