Journal article icon

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...

Expand abstract

Actions


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

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP