Colouring proximity graphs in the plane (Q1297436)

Given a set \(V\) of points in the plane and given \(d>0\), let \(G(V,d)\) denote the graph with vertex set \(V\) and with distinct vertices adjacent whenever the Euclidean distance between them is less than \(d\). In this paper the case when the set \(V\) has finite positive upper density \(\sigma \) and \(d\) is large is investigated. It is proved that, as \(d\rightarrow \infty \), the chromatic number \(\chi (G(V,d))\) divided by \(d^{2}\) tends to the limit \(\sigma 3^{0.5}/2\), and the ratio of the chromatic number \(\chi (G(V,d))\) to the clique number \(\omega (G(V,d))\) tends to \(2\cdot 3^{0.5}/ \pi \sim 1.103 \). Notice that one application where this problem arises is the design of cellular telephone networks, where it is needed to assign radio channels (colours) to transmitters (points in \(V\)) to avoid interference.