On the chromatic number of random geometric graphs
Colin McDiarmid, Müller, Tobias · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2011
Given independent random points X1,..., Xn ∈ Rd with common probability distribution ν, and a positive distance r = r(n)> 0, we construct a random geometric graph Gn with vertex set {1,..., n} where distinct i and j are adjacent when ‖Xi − Xj ‖ ≤ r. Here ‖. ‖ may be any norm on Rd, and ν may be any probability distribution on Rd with a bounded density function. We consider the chromatic number χ(Gn) of Gn and its relation to the clique number ω(Gn) as n → ∞. Both McDiarmid [11] ln n and Penrose [15] considered the range of r when r ≪ ( n)1/d and the range when ln n r ≫ ( n)1/d, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider t ln n