Journal article

### On the chromatic number of random geometric graphs

Abstract:

Given independent random points X1,...,Xn ∈ℝd 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 {double pipe}Xi-Xj{double pipe}≤r. Here {double pipe}·{double pipe} may be any norm on ℝd, and ν may be any probability distribution on ℝd with a bounded density function. We consider the chromatic number χ(Gn) of Gn and its relation to the clique number ω(Gn) as n...

### Access Document

Publisher copy:
10.1007/s00493-011-2403-3

### Authors

Journal:
Combinatorica
Volume:
31
Issue:
4
Pages:
423-488
Publication date:
2011-11-05
DOI:
ISSN:
0209-9683
URN:
uuid:c0c509ae-a011-4a4a-971a-05688d7373bd
Source identifiers:
216469
Local pid:
pubs:216469
Language:
English